hdu 4417 区间内比h小的数 线段树

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<queue>
  7 using namespace std;
  8 #define for0n for(i=0;i<n;i++)
  9 #define for1n for(i=1;i<=n;i++)
 10 #define for0m for(i=0;i<m;i++)
 11 #define for1m for(i=1;i<=m;i++)
 12 #define cl(a) memset(a,0,sizeof(a))
 13 #define w12 while(scanf("%d%d",&n,&m)!=EOF)
 14 #define s12 scanf("%d%d",&n,&m);
 15 #define sa scanf("%d",a[i]);
 16 #define sb scanf("%d",b[i]);
 17 #define lson l,mid,rt<<1
 18 #define rson mid+1,r,rt<<1|1
 19 #define mid ((l+r)>>1)
 20 #define root 1,n,1
 21 const int MAXN=100015;
 22 int sum[MAXN<<2];
 23 int n,m,t;
 24 void pushup(int rt)
 25 {
 26     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
 27 }
 28 void update(int pos,int l,int r,int rt)
 29 {
 30     if(l==r)
 31     {
 32         sum[rt]+=1;
 33         return;
 34     }
 35     if(pos<=mid) update(pos,lson);
 36     else update(pos,rson);
 37     pushup(rt);
 38 }
 39 int query(int L,int R,int l,int r,int rt)
 40 {
 41     if(l>=L&&r<=R)
 42     {
 43         return sum[rt];
 44     }
 45     int ret=0;
 46     if(L<=mid)
 47     {
 48          ret+=query(L,R,lson);
 49     }
 50     if(R>mid)
 51     {
 52         ret+=query(L,R,rson);
 53     }
 54     return ret;
 55 }
 56 struct Node
 57 {
 58     int s,e,h,id;
 59     void in()
 60     {
 61         scanf("%d%d%d",&s,&e,&h);
 62         s++;
 63         e++;
 64     }
 65 }node[MAXN];
 66 struct ss
 67 {
 68     int id,v;
 69 }a[MAXN];
 70 bool cmp1(Node a,Node b)
 71 {
 72     return a.h<b.h;
 73 }
 74 bool cmp2(ss a,ss b)
 75 {
 76     return a.v<b.v;
 77 }
 78 int as[MAXN];
 79 int main()
 80 {
 81     int i,j,k;
 82     #ifndef ONLINE_JUDGE
 83     freopen("1.in","r",stdin);
 84     #endif
 85     scanf("%d",&t);
 86     int iCase=0;
 87     while(t--)
 88     {
 89         iCase++;
 90         s12;
 91         for1n
 92         {
 93             scanf("%d",&a[i].v);
 94             a[i].id=i;
 95         }
 96         sort(a+1,a+n+1,cmp2);
 97         for0m
 98         {
 99             node[i].in();
100             node[i].id=i;
101         }
102         sort(node,node+m,cmp1);
103         cl(sum);
104         i=1;j=0;
105         while(j<m)
106         {
107             while(i<=n)  //小于j.h的高度的砖块加入线段树
108             {
109                 if(a[i].v>node[j].h)break;
110                 update(a[i].id,root);
111                 i++;
112             }
113             while(j<m)
114             {
115                 if(i<=n&&node[j].h>=a[i].v)break;
116                 as[node[j].id]=query(node[j].s,node[j].e,root);
117                 j++;
118             }
119         }
120         printf("Case %d:\n",iCase);
121         for(int i=0;i<m;i++)
122           printf("%d\n",as[i]);
123     }
124     return 0;
125 }