题目链接  

密码 acmore

还是感觉不怎么会线段树，还是得给自己另外多找点题目练练

Problem A

树状数组+离线操作见

 

Problem B

见

 

Problem C

题目意思是说给出一些星星的坐标，他们每个星星的等级是按照每个星星左下方星星的数目来定的，即所有点中满足x<x0,y<y0的点的数目就是这个店的等级。求每个等级的星星有多少个。

由于题目给出的坐标中y是按照升序给出的，所以我们只需要每输入一个坐标，就先查询它的x坐标的前方有多少个点，再将这个点插入到坐标轴中去，这样的话就可以保证每次查询的都是当前点的左下方的点的数目。这样的话就可以用树状数组来记录从1~x的区间内有多少个已经被标记的点。

1 #include 
     
       2 #include 
      
        3 #define mem(a) memset(a,0,sizeof(a)) 4 #define MAX(a , b) ((a) > (b) ? (a) : (b)) 5  6 int TreeArray[32005], N; 7 int ans[32005]; 8 int X[15005], Y; 9 10 int LowBit(int x)11 {12     return x&(-x);13 }14 15 int GetSum(int k)//返回区间1~k有多少个点16 {17     int sum = 0;18     while(k>=1)19     {20         sum += TreeArray[k];21         k -= LowBit(k);22     }23     return sum;24 }25 26 void Edit(int k,int Len)//插入一个点27 {28     while(k<=Len)29     {30         TreeArray[k] += 1;31         k += LowBit(k);32     }33 }34 35 int main()36 {37     while(~scanf("%d", &N))38     {39         mem(ans); mem(TreeArray);40         mem(X);41         int Max = 0;42         for(int i=1;i<=N;i++)43         {44             scanf("%d%d", &X[i], &Y);//其实不用吧每个点记录下来，可以每次都直接在区间1~32000内查找45             X[i]+=1;//由于题目说x有可能为0，而树状数组不可以记录点0，所以全部的x都+146             Max = MAX(X[i], Max);//我是想要找出区间最大坐标，然后在1到最大区间内查询47         }48         for(int i=1;i<=N;i++)49         {50             ans[GetSum(X[i])]++;//先查询51             Edit(X[i], Max);//后把点插入到坐标中去52         }53         for(int i=0;i
      
     

 

Problem D

线段树的基本操作，区间查询和节点修改

虽然此题比较简单，但是有一点学到的就是代码风格，要学会尽量让代码清晰易懂

1 #include 
     
       2 #include 
      
        3 #define MAX(a, b) ((a) > (b) ? (a) : (b)) 4 #define mem(a) memset(a, 0, sizeof(a)) 5 #define lson k<<1, l, mid 6 #define rson k<<1|1, mid+1, r 7 #define MAXN 200005 8  9 int Max[MAXN<<2], N, M;10 11 void edit(int k, int l,int r, int num, int v)12 {13     if(l == r)14     {15         Max[k] = v;16         return ;17     }18     int mid = (l+r)>>1;19     if(num <= mid)edit(lson, num, v);20     else edit(rson, num, v);21     Max[k] = MAX(Max[k<<1], Max[k<<1|1]);22 }23 24 int query(int k,int l,int r,int L,int R)25 {26     if(L<=l && r<=R)return Max[k];27     int mid = (l+r)>>1, Lans=0, Rans =0;28     if(L <= mid) Lans = query(lson, L, R);29     if(R > mid) Rans = query(rson, L, R);30     return MAX(Lans, Rans);31 }32 33 int main()34 {35     while(~scanf("%d %d", &N, &M))36     {37         int A, B;38         char ch; mem(Max);39         for(int i=1;i<=N;i++)40         {41             scanf("%d%*c", &A);42             edit(1,1,N,i,A);43         }44         for(int i=0;i
      
     

 

Problem E

一样都是基本操作

1 #include 
     
       2 #include 
      
        3 #define INF 1000010 4 #define mem(a) memset(a,0,sizeof(a)) 5 #define lson k<<1, l, mid 6 #define rson k<<1|1,mid+1, r 7 #define MAX(a,b) (a>b?a:b) 8 #define MIN(a,b) (a
       
        >1;30     if(num <= mid) edit(lson, num, val);31     else edit(rson,num,val);32     minH[k] = MIN(minH[k<<1], minH[k<<1|1]);33     maxH[k] = MAX(maxH[k<<1], maxH[k<<1|1]);34 }35 36 int query(int k,int l,int r,int L,int R,int IsMin)37 {38     if(L<=l && r<=R) return IsMin ? minH[k] : maxH[k];39     int mid = (l+r)>>1, Lval=INF, Rval=INF;40     if(L <= mid) Lval = query(lson,L,R,IsMin);41     if(R > mid) Rval = query(rson,L,R,IsMin);42     if(IsMin) return MIN(Lval, Rval);43     return MAX((Lval==INF?-INF:Lval), (Rval==INF?-INF:Rval));44 }45 46 int main()47 {48     while(~scanf("%d%d", &N, &M))49     {50         init();  int h;51         for(int i=1;i<=N;i++)52         {53             scanf("%d", &h);54             edit(1,1,N,i,h);55         }56         int  A, B;57         for(int i=0;i
       
      
     

 

Problem G

见