hdu 4417(2012 杭州网络赛)

唉，比赛的时候怎么都不会啊！！

题解：http://blog.csdn.net/acm_cxlove/article/details/8014170

划分树+二分答案：划分树可以方便的求解k-number。再利用二分答案，即区间内小于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:\n",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\n",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\n",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:\n",cas++);
106         for(int i=1;i<=m;i++)
107             printf("%d\n",ans[i]);
108 
109     }
110     return 0;
111 }