hdu 4417 (2012 항주 인터넷 경기)
34395 단어 2012
문제 풀이: http://blog.csdn.net/acm_cxlove/article/details/8014170
나 무 를 나 누 기 + 2 분 답: 나 무 를 나 누 면 k - number 를 쉽게 풀 수 있 습 니 다.2 분 의 답, 즉 구간 내 h 보다 작은 개수 (최대 r - l + 1, 최소 0) 를 이용 합 니 다.
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5
6 using namespace std;
7
8 #define ls rt<<1
9 #define rs rt<<1|1
10 #define lson l,m,ls
11 #define rson m+1,r,rs
12
13 #define MAXN 100010
14
15 struct Seg_Tree
16 {
17 int l,r;
18 }tt[MAXN<<2];
19 int len ,sorted[MAXN],toLeft[20][MAXN];
20 int val[20][MAXN];
21
22 void build(int d,int l,int r,int rt)
23 {
24 tt[rt].l=l;
25 tt[rt].r=r;
26 if(tt[rt].l == tt[rt].r) return ;
27 int m=(l+r)>>1;
28 int lsame = m-l+1;
29 for(int i=l;i<=r;i++)
30 if(val[d][i] < sorted[m])
31 lsame--;
32 int lpos =l,rpos=m+1,same=0;
33 for(int i=l;i<=r;i++)
34 {
35 if(i==l)
36 toLeft[d][i]=0;
37 else
38 toLeft[d][i] = toLeft[d][i-1];
39 if(val[d][i] < sorted[m])
40 {
41 toLeft[d][i]++;
42 val[d+1][lpos++] = val[d][i];
43 }
44 else if(val[d][i] > sorted[m])
45 val[d+1][rpos++] = val[d][i];
46 else
47 {
48 if(same<lsame)
49 {
50 same++;
51 toLeft[d][i]++;
52 val[d+1][lpos++] = val[d][i];
53 }
54 else
55 val[d+1][rpos++] = val[d][i];
56 }
57 }
58 build(d+1,lson);
59 build(d+1,rson);
60 }
61
62 int query(int k,int d,int l,int r,int rt)
63 {
64 if(l==r) return val[d][l];
65 int s,ss;
66 if(l == tt[rt].l)
67 {
68 s = toLeft[d][r];
69 ss=0;
70 }
71 else
72 {
73 s=toLeft[d][r] - toLeft[d][l-1];
74 ss=toLeft[d][l-1];
75 }
76 if(s >= k)
77 {
78 int newl = tt[rt].l+ss;
79 int newr = tt[rt].l+ss+s-1;
80 return query(k,d+1,newl,newr,ls);
81 }
82 else
83 {
84 int m = (tt[rt].l + tt[rt].r)>>1;
85 int bb = l-tt[rt].l -ss;
86 int b= r-l+1-s;
87 int newl = m+bb+1;
88 int newr = m+bb +b;
89 return query(k-s,d+1,newl,newr,rs);
90 }
91 }
92
93 int bsearch(int r,int h,int L,int R)//r
94 {
95 int l =0;
96 while(l<r)
97 {
98 int m = (l+r)>>1;// （ ）
99 if(query(m,0,L,R,1) >h)
100 r=m;
101 else
102 l=m+1;
103 }
104 return l;
105 }
106
107 int main()
108 {
109 int t,n,m;
110 scanf("%d",&t);
111 int cas=1;
112 while(t--)
113 {
114 scanf("%d%d",&n,&m);
115 for(int i=1;i<=n;i++)
116 {
117 scanf("%d",&val[0][i]);
118 sorted[i]=val[0][i];
119 }
120 sort(sorted+1,sorted+n+1);
121 build(0,1,n,1);
122 printf("Case %d:
",cas++);
123 while(m--)
124 {
125 int l,r,h;
126 scanf("%d%d%d",&l,&r,&h);
127 if(query(1,0,l+1,r+1,1) > h)
128 puts("0");
129 else if(query(r-l+1,0,l+1,r+1,1) <= h)
130 printf("%d
",r-l+1);
131 else
132 {
133 int res = bsearch(r-l+1,h,l+1,r+1);
134 while(res != 0 && query(res,0,l+1,r+1,1) >h)
135 res--;
136 printf("%d
",res);
137 }
138 }
139 }
140 return 0;
141 }원래 모든 질문 을 읽 고 H 에 따라 어 릴 때 부터 큰 순서 로 정렬 합 니 다.그리고 모든 결점 에 대해 서도 작은 것 에서 큰 것 으로 정렬 한 다음 에 조회 한 H 에 따라 H 보다 작은 점 을 선분 나무 에 넣 고 그 다음 에 아주 간단 한 구간 과..........................................................
나중에 쓴 오프라인 트 리:
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cmath>
5 #include <algorithm>
6
7 using namespace std;
8
9 #define mid (l+r)>>1
10 #define ls rt<<1
11 #define rs rt<<1|1
12 #define lson l,m,rt<<1
13 #define rson m+1,r,rt<<1|1
14
15 #define MAXN 100010
16
17 int sum[MAXN<<2],ans[MAXN];
18
19 struct Que
20 {
21 int l,r,h,id;
22 }Q[MAXN];
23 struct node
24 {
25 int h,id;
26 }in[MAXN];
27 int n,m;
28 bool cmp1(const Que &a,const Que &b)
29 {
30 return a.h<b.h;
31 }
32 bool cmp2(const node & a,const node &b)
33 {
34 return a.h<b.h;
35 }
36 void pushup(int rt)
37 {
38 sum[rt]=sum[ls]+sum[rs];
39 }
40
41 void build(int l,int r,int rt)
42 {
43 sum[rt]=0;
44 if(l==r) return;
45 int m = mid;
46 build(lson);
47 build(rson);
48 }
49 void update(int p,int q,int l,int r,int rt)
50 {
51 if(l==r)
52 {
53 sum[rt]+=q;
54 return ;
55 }
56 int m=mid;
57 if(p<=m) update(p,q,lson);
58 else update(p,q,rson);
59 pushup(rt);
60 }
61 int query(int L,int R,int l,int r,int rt)
62 {
63 if(L<=l && r<=R)
64 return sum[rt];
65 int m=mid;
66 int ret=0;
67 if(L<=m) ret+=query(L,R,lson);
68 if(m<R) ret+=query(L,R,rson);
69 return ret;
70 }
71
72 int main()
73 {
74 int t;
75 scanf("%d",&t);
76 int cas=1;
77 while(t--)
78 {
79 scanf("%d%d",&n,&m);
80 for(int i=0;i<n;i++)
81 {
82 scanf("%d",&in[i].h);
83 in[i].id=i+1;
84 }
85 for(int i=0;i<m;i++)
86 {
87 scanf("%d%d%d",&Q[i].l,&Q[i].r,&Q[i].h);
88 Q[i].id=i+1;
89 }
90 build(1,MAXN,1);
91 sort(Q,Q+m,cmp1);
92 sort(in,in+n,cmp2);
93
94 int i=0,j=0;
95 while(i<m)
96 {
97 while(in[j].h<=Q[i].h)
98 {
99 update(in[j].id,1,1,MAXN,1);
100 j++;
101 }
102 ans[Q[i].id]=query(Q[i].l+1,Q[i].r+1,1,MAXN,1);
103 i++;
104 }
105 printf("Case %d:
",cas++);
106 for(int i=1;i<=m;i++)
107 printf("%d
",ans[i]);
108
109 }
110 return 0;
111 }이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
문제의 진정한 원인 찾기: 20121021 서버 장애 처리 경험(당초 성능을 고려하여tempdb 데이터베이스 파일을 비RAID5의 독립 하드디스크에 놓았습니다.) 파일이 존재했지만 갑자기 이 하드디스크에 다른 폴더가 많이 보이지 않는 것을 발견했습니다.RAID5가 아닌 이 독립...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
