[关闭]
@ivorysi 2018-01-02T08:54:57.000000Z 字数 40621 阅读 789

数据结构（2）学习笔记

笔记

BZOJ 1588: [HNOI2002]营业额统计

Description

营业额统计 Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况： 该天的最小波动值 当最小波动值越大时，就说明营业情况越不稳定。 而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。 第一天的最小波动值为第一天的营业额。  输入输出要求

Input

第一行为正整数 ，表示该公司从成立一直到现在的天数，接下来的n行每行有一个整数(有可能有负数) ，表示第i
天公司的营业额。
天数n<=32767,
每天的营业额ai <= 1,000,000。
最后结果T<=2^31

Output

输出文件仅有一个正整数，即Sigma(每天最小的波动值) 。结果小于2^31 。

Sample Input

6
5
1
2
5
4
6

Sample Output

12

题解

splay求前驱，求后继
也就是把这个点旋转到根后，前驱是它左儿子的最右儿子，后继是它右儿子的最左儿子

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <set>
  8. #include <map>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define MAXN 300005
  13. //#define ivorysi
  14. using namespace std;
  15. typedef long long ll;
  16. int n;
  17. struct node {
  18.     int lc,rc,fa,val;
  19. }tr[MAXN];
  20. int nodecnt,root,ans;
  22. inline void rotate(int u) {
  23.     int v=tr[u].fa;int w=tr[v].fa;
  24.     int b= (u==tr[v].lc) ? tr[u].rc : tr[u].lc;
  25.     tr[v].fa=u;tr[u].fa=w;
  26.     if(b) tr[b].fa=v;
  27.     if(w) {(v==tr[w].lc ? tr[w].lc : tr[w].rc) =u; }
  28.     if(u==tr[v].lc) {tr[u].rc=v;tr[v].lc=b;}
  29.     else {tr[u].lc=v;tr[v].rc=b;}
  30. }
  31. int which(int u) {
  32.     return tr[tr[u].fa].rc==u;
  33. }
  34. void splay(int u,int tar) {
  35.     while(tr[u].fa!=tar) {
  36.     if(tr[tr[u].fa].fa!=tar) {
  37.         if(which(u)==which(tr[u].fa)) rotate(tr[u].fa);
  38.         else rotate(u);
  39.     }
  40.     rotate(u);
  41.     }
  42.     if(!tar) root=u;
  43. }
  44. void insert(int val) {
  45.     int u=root,v=0,dir;
  46.     while(u) {
  47.     v=u;
  48.     if(val>tr[u].val) {
  49.         u=tr[u].rc;
  50.         dir=1;
  51.     }
  52.     else {
  53.         u=tr[u].lc;
  54.         dir=0;
  55.     }
  56.     }
  57.     u=++nodecnt;
  58.     tr[u].val=val;tr[u].fa=v;
  59.     if(dir==0) tr[v].lc=u;
  60.     else tr[v].rc=u;
  61.     splay(u,0);
  62. }
  63. int query() {
  64.     int res=0x7fffffff;
  65.     int suf=tr[root].rc,pre=tr[root].lc;
  66.     while(pre && tr[pre].rc) {pre=tr[pre].rc;}
  67.     while(suf && tr[suf].lc) {suf=tr[suf].lc;}
  68.     if(pre) res=min(res,tr[root].val-tr[pre].val);
  69.     if(suf) res=min(res,tr[suf].val-tr[root].val);
  70.     return res;
  71. }
  73. int main() {
  74. #ifdef ivorysi
  75.     freopen("f1.in","r",stdin);
  76. #endif
  77.     int v;
  78.     scanf("%d%d",&n,&v);
  79.     tr[++nodecnt].val=v;
  80.     ans+=v;
  81.     root=nodecnt;
  82.     xiaosiji(i,1,n) {
  83.     scanf("%d",&v);
  84.     insert(v);
  85.     ans+=query();
  86.     }
  87.     printf("%d\n",ans);
  88. }

BZOJ 1208: [HNOI2004]宠物收养所

Description

最近，阿Q开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物，阿Q根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个正整数，a<2^31），而他也给每个处在收养所的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养所总是会有两种情况发生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少。 1． 被遗弃的宠物过多时，假若到来一个领养者，这个领养者希望领养的宠物的特点值为a，那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。（任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的）如果有两只满足要求的宠物，即存在两只宠物他们的特点值分别为a-b和a+b，那么领养者将会领养特点值为a-b的那只宠物。 2．收养宠物的人过多，假若到来一只被收养的宠物，那么哪个领养者能够领养它呢？能够领养它的领养者，是那个希望被领养宠物的特点值最接近该宠物特点值的领养者，如果该宠物的特点值为a，存在两个领养者他们希望领养宠物的特点值分别为a-b和a+b，那么特点值为a-b的那个领养者将成功领养该宠物。 一个领养者领养了一个特点值为a的宠物，而它本身希望领养的宠物的特点值为b，那么这个领养者的不满意程度为abs(a-b)。
【任务描述】你得到了一年当中，领养者和被收养宠物到来收养所的情况，希望你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时，收养所里面既没有宠物，也没有领养者。

Input

第一行为一个正整数n，n<=80000，表示一年当中来到收养所的宠物和领养者的总数。接下来的n行，按到来时间的先后顺序描述了一年当中来到收养所的宠物和领养者的情况。每行有两个正整数a, b，其中a=0表示宠物，a=1表示领养者，b表示宠物的特点值或是领养者希望领养宠物的特点值。（同一时间呆在收养所中的，要么全是宠物，要么全是领养者，这些宠物和领养者的个数不会超过10000个）

Output

仅有一个正整数，表示一年当中所有收养了宠物的领养者的不满意程度的总和mod 1000000以后的结果。

Sample Input

5
0 2
0 4
1 3
1 2
1 5

Sample Output

3
(abs(3-2) + abs(2-4)=3，最后一个领养者没有宠物可以领养)

题解

这道题如果找前驱直接把这个节点插入然后旋到根再去找前驱后继会T，直接利用二分查找树的性质去找前驱后继就好……
这里翻了个错误就是合并两个子树的时候没有把另一棵树的父亲节点更新

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <set>
  8. #include <map>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define MAXN 300005
  13. #define mod 1000000
  14. //#define ivorysi
  15. using namespace std;
  16. typedef long long ll;
  17. int n,t;
  18. int val,ans,now;
  19. struct node {
  20.     node *lc,*rc,*fa;
  21.     int val;
  22. }*root,*pre,*suf;
  23. int which(node *x) {
  24.     return x->fa->rc == x;
  25. }
  26. void rotate(node *u) {
  27.     node *v=u->fa,*w=v->fa;
  28.     node *b= (u==v->lc) ? u->rc : u->lc;
  29.     v->fa=u;u->fa=w;
  30.     if(b!=NULL) b->fa=v;
  31.     if(w!=NULL) {
  32.     (v == w->lc ? w->lc : w->rc ) = u;  
  33.     }
  34.     if(u == v->rc) { v->rc = b; u->lc = v;}
  35.     else {v->lc = b; u->rc = v;}
  36. }
  37. void splay(node *x,node *tar) {
  38.     while(x->fa!=tar) {
  39.     if(x->fa->fa != tar) {
  40.         if(which(x) == which(x->fa)) {rotate(x->fa);}
  41.         else rotate(x);
  42.     }
  43.     rotate(x);
  44.     }
  45.     if(tar==NULL) {
  46.     root=x;
  47.     }
  48. }
  49. void insert(int val) {
  50.     node *x=root,*f=NULL;
  51.     int dir;
  52.     while(x!=NULL) {
  53.     f=x;
  54.     if(val > x->val) {x=x->rc;dir=1;}
  55.     else {x=x->lc;dir=0;}
  56.     }
  57.     x=new node;
  58.     x->val=val;x->fa=f;x->lc=x->rc=NULL;
  59.     if(f!=NULL) {
  60.     (dir==0 ? f->lc : f->rc)  = x;
  61.     }
  62.     splay(x,NULL);
  63. }
  64. node* join(node *s1,node *s2) {
  65.     if(s1==NULL) return s2;
  66.     if(s2==NULL) return s1;
  67.     node *x=s1;
  68.     while(x->rc != NULL) x = x->rc;
  69.     splay(x,s1->fa);
  70.     x->rc = s2;
  71.     s2->fa = x;//忘记更新父亲了……gg
  72.     return x;
  73. }
  74. void del(node *x) {
  75.     splay(x,NULL);
  76.     root=join(root->lc,root->rc);
  77.     if(root!=NULL) root->fa=NULL;
  78. }
  79. void ask_before(node *now,int val) {
  80.     if(now==NULL) return;
  81.     if(now->val <= val) {
  82.     pre=now;
  83.     ask_before(now->rc,val);
  84.     }
  85.     else {
  86.     ask_before(now->lc,val);
  87.     }
  88. }
  89. void ask_after(node *now,int val) {
  90.     if(now==NULL) return;
  91.     if(now->val>=val) {
  92.     suf=now;
  93.     ask_after(now->lc,val);
  94.     }
  95.     else {
  96.     ask_after(now->rc,val);
  97.     }
  98. }
  99. int main() {
  100. #ifdef ivorysi
  101.     freopen("f1.in","r",stdin);
  102. #endif
  103.     now=-1;
  104.     scanf("%d",&n);
  105.     siji(i,1,n) {
  106.     scanf("%d%d",&t,&val);
  107.     if(now!=t && root!=NULL) {
  108.         pre=NULL;suf=NULL;
  109.         ask_before(root,val);
  110.         ask_after(root,val);
  111.         if(!pre) {ans+=(suf->val - val);del(suf);}
  112.         else if(!suf) {ans+=(val - pre->val);del(pre);}
  113.         else {
  114.         if(val - pre->val <= suf->val - val) {
  115.             ans+=(val - pre->val);
  116.             del(pre);
  117.         }
  118.         else {
  119.             ans+=(suf->val - val);
  120.             del(suf);
  121.         }
  122.         }
  123.         ans%=mod;
  124.     }
  125.     else {
  126.         insert(val);
  127.         now=t;
  128.     }
  129.     }
  130.     printf("%d\n",ans);
  131. }

BZOJ 1503: [NOI2004]郁闷的出纳员

Description

OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第k多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后告诉他答案。好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？

Input

Output

输出文件的行数为F命令的条数加一。对于每条F命令，你的程序要输出一行，仅包含一个整数，为当前工资第k多的员工所拿的工资数，如果k大于目前员工的数目，则输出-1。输出文件的最后一行包含一个整数，为离开公司的员工的总数。

Sample Input

9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2

Sample Output

10
20
-1
2

题解

这道题我们需要统计一棵树的大小
我们每次增加是对整棵树增加，所以我们可以维护一个delta
加入一个人 插入一个节点k-delta
每次加工资 delta+=k
每次减工资 delta-=k
然后插入节点min-delta，旋转到根，删除左子树，再把根作为根的右儿子
查找人按照二分查找树去查找即可

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <set>
  8. #include <map>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define MAXN 300005
  13. #define mod 1000000
  14. //#define ivorysi
  15. using namespace std;
  16. typedef long long ll;
  17. int n,cnt;
  18. ll minnum,delta;
  19. char op[5];
  20. struct node {
  21.     node *fa,*lc,*rc;
  22.     ll val;
  23.     int size;
  24. }*root;
  25. void update(node *u) {
  26.     u->size=1;
  27.     if(u->lc!=NULL) u->size+=u->lc->size;
  28.     if(u->rc!=NULL) u->size+=u->rc->size;
  29. }
  30. void rotate(node *u) {
  31.     node *v=u->fa,*w=v->fa;
  32.     node *b=(v->lc == u) ? u->rc : u->lc;
  33.     u->fa=w;v->fa=u;
  34.     if(b) b->fa=v;
  35.     if(w) {(w->lc==v ? w->lc : w->rc) = u;}
  36.     if(u==v->lc) {v->lc = b;u->rc = v;}
  37.     else {v->rc = b;u->lc = v;}
  38.     update(v);
  39. }
  40. int which(node *u) {
  41.     return u->fa->rc == u;
  42. }
  43. void splay(node *u,node *tar) {
  44.     while(u->fa!=tar) {
  45.     if(u->fa->fa!=tar) {
  46.         if(which(u) == which(u->fa)) rotate(u->fa);
  47.         else rotate(u);
  48.     }
  49.     rotate(u);
  50.     }
  51.     update(u);
  52.     if(tar==NULL) {root=u;}
  53. }
  54. void insert(ll val) {
  55.     node *u=root,*v=NULL;
  56.     int dir;
  57.     while(u) {
  58.     v=u;
  59.     ++v->size;
  60.     if(u->val >= val) {u=u->lc;dir=0;}
  61.     else {u = u->rc; dir=1;}
  62.     }
  63.     u=new node;
  64.     u->val=val;u->fa=v;u->size=1;u->lc=u->rc=NULL;
  65.     if(v) {
  66.     if(dir==0) v->lc=u;
  67.     else v->rc=u;
  68.     }
  69.     splay(u,NULL);
  70. }
  71. ll query(node *now,int s) {
  72.     int k = (now->lc!=NULL ? now->lc->size : 0);
  73.     if(k+1==s) return now->val;
  74.     else if(k>=s) {
  75.     return query(now->lc,s);
  76.     }
  77.     else {
  78.     return query(now->rc,s-k-1);
  79.     }
  80. }
  81. int main() {
  82. #ifdef ivorysi
  83.     freopen("f1.in","r",stdin);
  84. #endif
  85.     scanf("%d%lld",&n,&minnum);
  86.     delta=0;
  87.     int k;
  88.     siji(i,1,n) {
  89.     scanf("%s%d",op+1,&k);
  90.     if(op[1]=='I') {
  91.         if(k<minnum) {continue;}
  92.         insert((ll)k-delta);
  93.     }
  94.     else if(op[1]=='A') {
  95.         delta+=k;
  96.     }
  97.     else if(op[1]=='S') {
  98.         delta-=k;
  99.         insert(minnum-delta);
  100.         if(root->lc!=NULL) cnt+=root->lc->size;
  101.         root->lc=NULL;
  102.         root=root->rc;
  103.         if(root!=NULL) root->fa=NULL;
  104.     }
  105.     else {
  106.         if(root==NULL || root->size < k) puts("-1");
  107.         else {
  108.         printf("%lld\n",query(root,root->size - k +1)+delta);
  109.         }
  110.     }
  111.     }
  112.     printf("%d\n",cnt);
  113. }

BZOJ 1861: [Zjoi2006]Book 书架

Description

小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。 小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。不过小T的记忆力是非常好的，所以每次放书的时候至少能够将那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有X本书，那么放回去时这本书上面就只可能有X-1、X或X+1本书。 当然也有特殊情况，比如在看书的时候突然电话响了或者有朋友来访。这时候粗心的小T会随手把书放在书柜里所有书的最上面或者最下面，然后转身离开。 久而久之，小T的书柜里的书的顺序就会越来越乱，找到特定的编号的书就变得越来越困难。于是她想请你帮她编写一个图书管理程序，处理她看书时的一些操作，以及回答她的两个提问：(1)编号为X的书在书柜的什么位置；(2)从上到下第i本书的编号是多少。

Input

第一行有两个数n，m，分别表示书的个数以及命令的条数；第二行为n个正整数：第i个数表示初始时从上至下第i个位置放置的书的编号；第三行到m+2行，每行一条命令。命令有5种形式： 1． Top S——表示把编号为S的书房在最上面。 2． Bottom S——表示把编号为S的书房在最下面。 3． Insert S T——T∈{-1，0，1}，若编号为S的书上面有X本书，则这条命令表示把这本书放回去后它的上面有X+T本书； 4． Ask S——询问编号为S的书的上面目前有多少本书。 5． Query S——询问从上面数起的第S本书的编号。

Output

对于每一条Ask或Query语句你应该输出一行，一个数，代表询问的答案。

Sample Input

10 10
1 3 2 7 5 8 10 4 9 6
Query 3
Top 5
Ask 6
Bottom 3
Ask 3
Top 6
Insert 4 -1
Query 5
Query 2
Ask 2

Sample Output

2
9
9
7
5
3

HINT

数据范围

100%的数据，n,m < = 80000

题解

top 删除这个点，然后不断的走到根的最左端
bottom 删除这个点，不断走到根的最右端
insert +1 这个点旋转到根，找到这个点的前驱，将前驱旋转为它的左儿子，将这个点插在前驱和前驱的左子树之间，这个点的右子树交给前驱
insert -1 这个点旋转到根，找到这个点的后继，将后继旋转为它的右儿子，将这个点插在后继和后继的右子树之间，这个点的左子树交给后继
ask 这个点旋转到根，左子树的大小即为答案
query 按照二分查找树的性质查找即可

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <set>
  8. #include <map>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define MAXN 100005
  13. #define mod 1000000
  14. //#define ivorysi
  15. using namespace std;
  16. typedef long long ll;
  17. int n,m;
  18. int id[MAXN];
  19. struct node {
  20.     node *fa,*lc,*rc;
  21.     int num;
  22.     int size;
  23. }*root,*pool[MAXN];
  24. char op[35];
  25. void update(node *u) {
  26.     u->size=1;
  27.     if(u->lc!=NULL) u->size+=u->lc->size;
  28.     if(u->rc!=NULL) u->size+=u->rc->size;
  29. }
  30. int which(node *u) {
  31.     return u->fa->rc==u;
  32. }
  33. void rotate(node *u) {
  34.     node *v=u->fa,*w=v->fa;
  35.     node *b= (v->lc == u) ? u->rc : u->lc;
  36.     update(v);
  37.     u->fa=w;v->fa=u;
  38.     if(b) b->fa=v;
  39.     if(w) {(v==w->lc ? w->lc : w->rc) = u;}
  40.     if(v->lc==u) { v->lc=b; u->rc=v;}
  41.     else {v->rc=b; u->lc=v;}
  42.     update(v);
  43. }
  44. void splay(node *u,node *tar) {
  45.     while(u->fa!=tar) {
  46.     if(u->fa->fa!=tar) {
  47.         if(which(u)==which(u->fa)) rotate(u->fa);
  48.         else rotate(u);
  49.     }
  50.     rotate(u);
  51.     }
  52.     update(u);
  53.     if(tar==NULL) root=u;
  54. }
  55. node *build(int l,int r) {
  56.     if(l>r) return NULL;
  57.     if(l==r) return pool[id[l]];
  58.     int mid=(l+r)>>1;
  59.     node *res=pool[id[mid+1]];
  60.     res->lc=build(l,mid);
  61.     res->rc=build(mid+2,r);
  62.     if(res->lc) res->lc->fa=res;
  63.     if(res->rc) res->rc->fa=res;
  64.     update(res);
  65.     return res;
  66. }
  67. node* join(node *s1,node *s2) {
  68.     if(s1==NULL) return s2;
  69.     if(s2==NULL) return s1;
  70.     node *x=s1;
  71.     while(x->rc!=NULL) x=x->rc;
  72.     splay(x,s1->fa);
  73.     x->rc=s2;
  74.     s2->fa=x;
  75.     update(x);
  76.     return x;
  77. }
  78. void del(node *u) {
  79.     splay(u,NULL);
  80.     root=join(u->lc,u->rc);
  81.     u->fa=u->lc=u->rc=NULL;
  82.     root->fa=NULL;
  83. }
  84. void Top(node *u) {
  85.     del(u);
  86.     node *x=root;
  87.     while(x->lc!=NULL) {++x->size;x=x->lc;}
  88.     x->lc=u;
  89.     u->fa=x;
  90.     ++x->size;
  91.     u->size=1;
  92. }
  93. void Bottom(node *u) {
  94.     del(u);
  95.     node *x=root;
  96.     while(x->rc!=NULL) {++x->size;x=x->rc;}
  97.     x->rc=u;
  98.     u->fa=x;
  99.     ++x->size;
  100.     u->size=1;
  101. }
  102. void Insert_left(node *u) {
  103.     splay(u,NULL);
  104.     node *x=u->lc;
  105.     while(x->rc) x=x->rc;
  106.     splay(x,u);
  107.     u->lc=x->lc;
  108.     if(x->lc) x->lc->fa=u;
  109.     x->rc=u->rc;
  110.     if(u->rc) u->rc->fa=x;
  111.     u->rc=NULL;
  112.     x->lc=u;
  113.     u->fa=x;
  114.     root=x;
  115.     root->fa=NULL;
  116.     update(u);update(x);
  118. }
  119. void Insert_right(node *u) {
  120.     splay(u,NULL);
  121.     node *x=u->rc;
  122.     while(x->lc) x=x->lc;
  123.     splay(x,u);
  124.     u->rc=x->rc;
  125.     if(x->rc) x->rc->fa=u;
  126.     x->lc=u->lc;
  127.     if(u->lc) u->lc->fa=x;
  128.     u->lc=NULL;
  129.     x->rc=u;
  130.     u->fa=x;
  131.     root=x;
  132.     root->fa=NULL;
  133.     update(u);update(x);
  135. }
  136. int query(node *u,int s) {
  137.     int k=(u->lc!=NULL ? u->lc->size : 0);
  138.     if(k+1==s) return u->num;
  139.     else if(k>=s) {
  140.     return query(u->lc,s);
  141.     }
  142.     else {
  143.     return query(u->rc,s-k-1);
  144.     }
  145. }
  146. void init() {
  147.     scanf("%d%d",&n,&m);
  148.     siji(i,1,n) {
  149.     scanf("%d",&id[i]);
  150.     pool[i]=new node;
  151.     pool[i]->fa=pool[i]->lc=pool[i]->rc=NULL;
  152.     pool[i]->size=1;
  153.     pool[i]->num=i;
  154.     }
  155.     root=build(1,n);
  156. }
  157. int main() {
  158. #ifdef ivorysi
  159.     freopen("f1.in","r",stdin);
  160. #endif
  161.     init();
  162.     int s,t;
  163.     siji(i,1,m) {
  164.     scanf("%s",op+1);
  165.     scanf("%d",&s);
  166.     if(op[1]=='T') Top(pool[s]);
  167.     else if(op[1]=='B') Bottom(pool[s]);
  168.     else if(op[1]=='I') {
  169.         scanf("%d",&t);
  170.         if(t==0) continue;
  171.         if(t==-1) Insert_left(pool[s]);
  172.         if(t==1) Insert_right(pool[s]);
  173.     }
  174.     else if(op[1]=='A') {
  175.         splay(pool[s],NULL);
  176.         int res= (root->lc!=NULL ? root->lc->size : 0);
  177.         printf("%d\n",res);
  178.     }
  179.     else if(op[1]=='Q'){
  180.         printf("%d\n",query(root,s));
  181.     }
  182.     }
  183. }

BZOJ 3223: Tyvj 1729 文艺平衡树

Description

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1

Input

第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n

Output

输出一行n个数字，表示原始序列经过m次变换后的结果

Sample Input

5 3
1 3
1 3
1 4

Sample Output

4 3 2 1 5

HINT

N,M<=100000

题解

（PE是什么鬼啊！！！）
我们这回要用到打标记，打标记的精髓在于，根节点到这个节点的路上没有标记，那么结果一定会是正确的
这道题的翻转操作我们可以先设置两个哨兵节点，一前一后
我们翻转区间[l,r]可以找到第l-1个点和第r+1个点，把l-1旋转到根，r+1旋转成根的右儿子，再把r+1的左儿子打上翻转标记
我们在找l-1和r+1的点时下放翻转标记
最后查询的时候也要下放翻转标记

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <set>
  8. #include <map>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define MAXN 100010
  13. #define mod 1000000
  14. //#define ivorysi
  15. using namespace std;
  16. typedef long long ll;
  17. int n,m;
  18. int ans[MAXN],tot;
  19. struct node {
  20.     node *fa,*lc,*rc;
  21.     int size,num;
  22.     bool rev;
  23. }*root,*pool[MAXN];
  24. void update(node *u) {
  25.     u->size=1;
  26.     if(u->lc) u->size+=u->lc->size;
  27.     if(u->rc) u->size+=u->rc->size;
  28. }
  29. void pushdown(node *u) {
  30.     if(u->rev) {
  31.     swap(u->lc,u->rc);
  32.     if(u->lc) u->lc->rev ^= 1;
  33.     if(u->rc) u->rc->rev ^= 1;
  34.     u->rev=0;
  35.     } 
  36. }
  37. node *build(int l,int r) {
  38.     if(l>r) return NULL;
  39.     if(l==r) return pool[l];
  40.     int mid=(l+r)>>1;
  41.     node *res=pool[mid+1];
  42.     res->lc=build(l,mid);
  43.     res->rc=build(mid+2,r);
  44.     if(res->lc) res->lc->fa=res;
  45.     if(res->rc) res->rc->fa=res;
  46.     update(res);
  47.     return res;
  48. }
  49. void rotate(node *u) {
  50.     node *v=u->fa,*w=v->fa;
  51.     node *b= (u==v->lc) ? u->rc : u->lc;
  52.     v->fa=u;u->fa=w;
  53.     if(b) b->fa=v;
  54.     if(w) {(v==w->lc ? w->lc : w->rc) = u;}
  55.     if(u==v->lc) {v->lc=b; u->rc=v;}
  56.     else {v->rc=b;u->lc=v;}
  57.     update(v);
  58. }
  59. int which(node *u) {
  60.     return u->fa->rc==u;
  61. }
  62. void splay(node *u,node *tar) {
  63.     while(u->fa!=tar) {
  64.     if(u->fa->fa!=tar) {
  65.         if(which(u)==which(u->fa)) rotate(u->fa);
  66.         else rotate(u);
  67.     }
  68.     rotate(u);
  69.     }
  70.     update(u);
  71.     if(tar==NULL) root=u;
  72. }
  73. node *query(node *u,int s) {
  74.     pushdown(u);
  75.     int k=(u->lc!=NULL) ? u->lc->size : 0;
  76.     if(k+1==s) {
  77.     return u;
  78.     }
  79.     else if(k>=s) {
  80.     return query(u->lc,s);
  81.     }
  82.     else {
  83.     return query(u->rc,s-k-1);
  84.     }
  85. }
  86. void Reverse(int l,int r) {
  87.     node *pre=query(root,l-1),*suf=query(root,r+1);
  88.     splay(pre,NULL);
  89.     splay(suf,pre);
  90.     suf->lc->rev ^=1;
  91. }
  92. void dfs(node *u) {
  93.     pushdown(u);
  94.     if(u->lc) dfs(u->lc);
  95.     ans[++tot]=u->num;
  96.     if(u->rc) dfs(u->rc);
  97. }
  98. int main() {
  99. #ifdef ivorysi
  100.     freopen("f1.in","r",stdin);
  101. #endif
  102.     scanf("%d%d",&n,&m);
  103.     siji(i,1,n+2) {
  104.     pool[i]=new node;
  105.     pool[i]->fa=pool[i]->lc=pool[i]->rc=NULL;
  106.     pool[i]->size=1;
  107.     pool[i]->num=i;
  108.     pool[i]->rev=0;
  109.     }
  110.     root=build(1,n+2);
  111.     int a,b;
  112.     siji(i,1,m) {
  113.     scanf("%d%d",&a,&b);
  114.     Reverse(a+1,b+1);
  115.     }
  116.     dfs(root);
  117.     siji(i,2,n+1) {
  118.     printf("%d ",ans[i]-1);
  119.     }
  120. }

BZOJ 3224: Tyvj 1728 普通平衡树

Description

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)

Input

第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)

Output

对于操作3,4,5,6每行输出一个数，表示对应答案

Sample Input

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

Sample Output

106465
84185
492737

HINT

1.n的数据范围：n<=100000
2.每个数的数据范围：[-2e9,2e9]

题解

这道题本来是一道普通的平衡树题
但是我前缀后缀写挂了
如果找到一个点这个点的右儿子还大于我们要找的数，还要继续找右儿子的左儿子……

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <set>
  8. #include <map>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define MAXN 100010
  13. #define mod 1000000
  14. //#define ivorysi
  15. using namespace std;
  16. typedef long long ll;
  17. struct node {
  18.     node *fa,*lc,*rc;
  19.     int cnt,val,size;
  20. }*root;
  21. void update(node *u) {
  22.     u->size=u->cnt;
  23.     if(u->lc) u->size+=u->lc->size;
  24.     if(u->rc) u->size+=u->rc->size;
  25. }
  26. void rotate(node *u) {
  27.     node *v=u->fa,*w=v->fa;
  28.     node *b=(u==v->lc) ? u->rc : u->lc;
  29.     u->fa=w;v->fa=u;
  30.     if(b) b->fa=v;
  31.     if(w) {(w->lc == v ? w->lc : w->rc)=u;}
  32.     if(u==v->lc) {v->lc=b;u->rc=v;}
  33.     else {v->rc=b;u->lc=v;}
  34.     update(v);
  35. }
  36. int which(node *u) {
  37.     return u->fa->rc==u;
  38. }
  39. void splay(node *u,node *tar) {
  40.     while(u->fa!=tar) {
  41.     if(u->fa->fa!=tar) {
  42.         if(which(u)==which(u->fa)) rotate(u->fa);
  43.         else rotate(u);
  44.     }
  45.     rotate(u);
  46.     }
  47.     update(u);
  48.     if(tar==NULL) root=u;
  49. }
  50. void Insert(int val) {
  51.     node *u=root,*v=NULL;
  52.     int dir;
  53.     while(u) {
  54.     v=u;
  55.     ++v->size;
  56.     if(u->val == val) {++u->cnt;return;}
  57.     else if(u->val > val) {u=u->lc;dir=0;}
  58.     else {u=u->rc;dir=1;}
  59.     }
  60.     u=new node;
  61.     u->cnt=u->size=1;u->val=val;
  62.     u->fa=v;u->lc=u->rc=NULL;
  63.     if(v) {
  64.     (dir==0 ? v->lc : v->rc) =u;
  65.     }
  66.     splay(u,NULL);
  67. }
  68. node *findpos(node *u,int val) {
  69.     if(u->val==val) return u;
  70.     if(val < u->val) return findpos(u->lc,val);
  71.     else return findpos(u->rc,val);
  72. }
  73. node *join(node *s1,node *s2) {
  74.     if(s1==NULL) return s2;
  75.     if(s2==NULL) return s1;
  76.     node *x=s1;
  77.     while(x->rc) x=x->rc;
  78.     splay(x,s1->fa);
  79.     x->rc=s2;
  80.     s2->fa=x;
  81.     update(x);
  82.     return x;
  83. }
  84. void del(int val) {
  85.     node *x=findpos(root,val);
  86.     splay(x,NULL);
  87.     if(x->cnt>1) {--x->cnt;--x->size;}
  88.     else {
  89.     root=join(root->lc,root->rc);
  90.     if(root) root->fa=NULL;
  91.     }
  92. }
  93. int getpos(int val){
  94.     node *x=findpos(root,val);
  95.     splay(x,NULL);
  96.     int k= (x->lc!=NULL) ? x->lc->size : 0;
  97.     return k+1;
  98. }
  99. int query(node *u,int s) {
  100.     int k=(u->lc!=NULL) ? u->lc->size : 0;
  101.     if(k<s && (k + u->cnt)>=s) return u->val;
  102.     else if(k>=s) {
  103.     return query(u->lc,s);
  104.     }
  105.     else {
  106.     return query(u->rc,s- k - u->cnt);
  107.     }
  108. }
  109. node *pre,*suf;
  110. void ask_prev(node *u,int val) {
  111.     if(u==NULL) return;
  112.     if(u->val < val) {
  113.     pre=u;
  114.     ask_prev(u->rc,val);
  115.     }
  116.     else {
  117.     ask_prev(u->lc,val);
  118.     }
  119. }
  120. void ask_suffix(node *u,int val) {
  121.     if(u==NULL) return;
  122.     if(u->val > val) {
  123.     suf=u;
  124.     ask_suffix(u->lc,val);
  125.     }
  126.     else {
  127.     ask_suffix(u->rc,val);
  128.     }
  129. }
  130. int main() {
  131. #ifdef ivorysi
  132.     freopen("f1.in","r",stdin);
  133. #endif
  134.     int n;
  135.     int op,x;
  136.     scanf("%d",&n);
  137.     siji(i,1,n) {
  138.     scanf("%d%d",&op,&x);
  139.     if(op==1) {
  140.         Insert(x);
  141.     }
  142.     else if(op==2) {
  143.         del(x);
  144.     }
  145.     else if(op==3) {
  146.         printf("%d\n",getpos(x));
  147.     }
  148.     else if(op==4) {
  149.         printf("%d\n",query(root,x));
  150.     }
  151.     else if(op==5) {
  152.         ask_prev(root,x);
  153.         printf("%d\n",pre->val);
  154.     }
  155.     else {
  156.         ask_suffix(root,x);
  157.         printf("%d\n",suf->val);
  158.     }
  159.     }
  160. }

BZOJ 1014: [JSOI2008]火星人prefix

Description

火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方说，有这样一个字符串：madamimadam，
我们将这个字符串的各个字符予以标号：序号： 1 2 3 4 5 6 7 8 9 10 11 字符 m a d a m i m a d a m 现在，
火星人定义了一个函数LCQ(x, y)，表示：该字符串中第x个字符开始的字串，与该字符串中第y个字符开始的字串
，两个字串的公共前缀的长度。比方说，LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0 在研究LCQ函数的过程
中，火星人发现了这样的一个关联：如果把该字符串的所有后缀排好序，就可以很快地求出LCQ函数的值；同样，
如果求出了LCQ函数的值，也可以很快地将该字符串的后缀排好序。 尽管火星人聪明地找到了求取LCQ函数的快速
算法，但不甘心认输的地球人又给火星人出了个难题：在求取LCQ函数的同时，还可以改变字符串本身。具体地说
，可以更改字符串中某一个字符的值，也可以在字符串中的某一个位置插入一个字符。地球人想考验一下，在如此
复杂的问题中，火星人是否还能够做到很快地求取LCQ函数的值。

Input

第一行给出初始的字符串。第二行是一个非负整数M，表示操作的个数。接下来的M行，每行描述一个操作。操作有3种，如下所示
1、询问。语法：Qxy，x,y均为正整数。功能：计算LCQ(x,y)限制：1<=x,y<=当前字符串长度。
2、修改。语法：Rxd，x是正整数，d是字符。功能：将字符串中第x个数修改为字符d。限制：x不超过当前字
符串长度。
3、插入：语法：Ixd，x是非负整数，d是字符。功能：在字符串第x个字符之后插入字符d，如果x=0，则在字
符串开头插入。限制：x不超过当前字符串长度

Output

对于输入文件中每一个询问操作，你都应该输出对应的答案。一个答案一行。

Sample Input

madamimadam
7
Q 1 7
Q 4 8
Q 10 11
R 3 a
Q 1 7
I 10 a
Q 2 11

Sample Output

5
1
0
2
1

HINT

1、所有字符串自始至终都只有小写字母构成。
2、M<=150,000
3、字符串长度L自始至终都满足L<=100,000
4、询问操作的个数不超过10,000个。
对于第1，2个数据，字符串长度自始至终都不超过1,000
对于第3，4，5个数据，没有插入操作。

题解

这道题我们要考虑一个问题，就是hash可以用分配律来表示
然后我们如果要得到某一个串的hash值，我们可以把一个串的前一个字符转到根，然后这个串的后一个字符转到根的右儿子，这个字符的左儿子就是答案
然后我们就可以用普通的二分求lcp的方法求lcp了，真是妙啊

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <set>
  8. #include <map>
  9. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  10. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  11. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  12. #define MAXN 100010
  13. #define mod 99994711
  14. #define ba 823
  15. //#define ivorysi
  16. using namespace std;
  17. typedef long long ll;
  18. struct node {
  19.     node *fa,*lc,*rc;
  20.     int size;
  21.     ll val,c;
  22. }*root;
  23. char str[MAXN],op[10];
  24. ll e[MAXN];
  25. int n;
  26. void update(node *u) {
  27.     u->size=1;
  28.     if(u->lc) u->size+=u->lc->size;
  29.     if(u->rc) u->size+=u->rc->size;
  30.     int k=(u->lc!=NULL) ? u->lc->size : 0;
  31.     u->val=0;
  32.     if(u->lc) u->val+=u->lc->val;
  33.     u->val+=u->c * e[k]%mod;
  34.     if(u->rc) u->val+=u->rc->val * e[k+1]%mod;
  35.     u->val%=mod;
  36. }
  37. node *build(int l,int r) {
  38.     if(l>r) return NULL;
  39.     node *res=new node;
  40.     res->fa=res->lc=res->rc=NULL;
  41.     res->size=1;
  42.     if(l==r) {
  43.     res->val=(str[l]-'a'+1);
  44.     res->c=(str[l]-'a'+1);
  45.     return res;
  46.     }
  47.     int mid=(l+r)>>1;
  48.     res->val=(str[mid+1]-'a'+1);
  49.     res->c=(str[mid+1]-'a'+1);
  50.     res->lc=build(l,mid);
  51.     res->rc=build(mid+2,r);
  52.     if(res->lc) res->lc->fa=res;
  53.     if(res->rc) res->rc->fa=res;
  54.     update(res);
  55.     return res;
  56. }
  57. void rotate(node *u) {
  58.     node *v=u->fa,*w=v->fa;
  59.     node *b= (u==v->lc) ? u->rc : u->lc;
  60.     u->fa = w;v->fa = u;
  61.     if(b) b->fa = v;//always wrong....
  62.     if(w) {(w->lc == v ? w->lc : w->rc) = u;}
  63.     if(v->lc == u) {v->lc = b;u->rc=v;}
  64.     else {v->rc =b;u->lc=v;}
  65.     update(v);
  66. }
  67. int which(node *u) {
  68.     return u->fa->rc==u;
  69. }    
  70. void splay(node *u,node *tar) {
  71.     while(u->fa!=tar) {
  72.     if(u->fa->fa!=tar) {
  73.         if(which(u->fa)==which(u)) rotate(u->fa);
  74.         else rotate(u);
  75.     }
  76.     rotate(u);
  77.     }
  78.     update(u);
  79.     if(tar==NULL) root=u;
  80. }
  81. node *findpos(node *u,int s) {
  82.     int k=(u->lc!=NULL) ? u->lc->size : 0;
  83.     if(k+1==s) return u;
  84.     else if(k>=s) {
  85.     return findpos(u->lc,s);
  86.     }
  87.     else {
  88.     return findpos(u->rc,s-k-1);
  89.     }
  90. }
  91. void Insert(int x,char d) {
  92.     node *k=findpos(root,x);
  93.     splay(k,NULL);
  94.     node *p=new node;
  95.     p->fa=k;p->rc=k->rc;p->lc=NULL;
  96.     p->c=(d-'a'+1);
  97.     if(p->rc) p->rc->fa=p;
  98.     k->rc=p;
  99.     update(p);update(k);
  100. }
  101. void Refresh(int x,char d) {
  102.     node *k=findpos(root,x);
  103.     splay(k,NULL);
  104.     k->c = d-'a'+1;
  105.     update(k);
  106. }
  107. bool check(int l1,int r1,int l2,int r2) {
  108.     node *pre=findpos(root,l1-1);
  109.     node *suf=findpos(root,r1+1);
  110.     splay(pre,NULL);
  111.     splay(suf,pre);
  112.     ll res=suf->lc->val;
  113.     pre=findpos(root,l2-1);
  114.     suf=findpos(root,r2+1);
  115.     splay(pre,NULL);
  116.     splay(suf,pre);
  117.     res-=suf->lc->val;
  118.     res=(res%mod+mod)%mod;
  119.     return res==0;
  120. }
  121. int query(int a,int b) {
  122.     int l=0,r=root->size-max(a,b);
  123.     while(l<r) {
  124.     int mid=(l+r+1)>>1;
  125.     if(check(a,a+mid-1,b,b+mid-1)) l=mid;
  126.     else r=mid-1;
  127.     }
  128.     return l;
  129. }
  130. int main() {
  131. #ifdef ivorysi
  132.     freopen("f1.in","r",stdin);
  133. #endif
  134.     e[0]=1;
  135.     siji(i,1,100005) {
  136.     e[i]=e[i-1]*ba%mod;
  137.     }
  138.     scanf("%s",str+2);
  139.     int len=strlen(str+2);
  140.     str[1]='a';
  141.     str[len+2]='a';
  142.     root=build(1,len+2);
  143.     scanf("%d",&n);
  144.     int x,y;
  145.     char d[5];
  146.     siji(i,1,n) {
  147.     scanf("%s",op+1);
  148.     if(op[1]=='I') {
  149.         scanf("%d%s",&x,d+1);
  150.         Insert(x+1,d[1]);
  151.     }
  152.     else if(op[1]=='R') {
  153.         scanf("%d%s",&x,d+1);
  154.         Refresh(x+1,d[1]);
  155.     }
  156.     else {
  157.         scanf("%d%d",&x,&y);
  158.         printf("%d\n",query(x+1,y+1));
  159.     }
  160.     }
  161. }

1500: [NOI2005]维修数列

Description

给出一棵树支持插入一些数
删除一个连续序列里的数
将一段数全部改为同一个数
将一段数反转
求区间和
求区间最大子段和

Input

输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。
第2行包含N个数字，描述初始时的数列。
以下M行，每行一条命令，格式参见问题描述中的表格。
任何时刻数列中最多含有500 000个数，数列中任何一个数字均在[-1 000, 1 000]内。
插入的数字总数不超过4 000 000个，输入文件大小不超过20MBytes。

Output

对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。

Sample Input

9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM

Sample Output

-1
10
1
10

题解

这道题和文艺平衡树的反转标记还不太一样，因为左右儿子如果不反转的话还有可能影响根节点的值的大小如何更新

我们要维护父亲，左儿子，右儿子
树的大小，右侧最大值，左侧最大值，所有树的总和，子树里的最大子段和，这个结点的数是多少
是否被反转，是否被覆盖，覆盖的值是多少

插入 把区间的前一个转到根，后一个转到根的右儿子，左子树插入建好的一棵树，像建线段树那样建，这样比较平衡
删除 由于我们要回收空间，我们还要遍历一下这棵子树，然后delete掉所有
修改 打标记，注意下传的时候左右儿子都要下传，lmax和rmax改成c和c×size里较大的一个
反转 打标记，注意下传的时候左右儿子都要下传
求区间和 维护sum即可
求最大子段和 用左右子树的最大子段和，和包含根节点的最大子段和来更新

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  4. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  5. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  6. //#define ivorysi
  7. using namespace std;
  8. typedef long long ll;
  9. struct node {
  10.     node *fa,*lc,*rc;
  11.     int size;
  12.     int rmax,lmax,sum,maxval,cover,val;
  13.     bool rev,iscover;
  14. }*root;
  15. char s[25];
  16. int n,m,a[1000005];
  17. void update(node *u) {
  18.     u->size=1;
  19.     u->sum=u->val;
  20.     u->maxval=u->val;
  21.     if(u->lc && u->lc->rmax>0) u->maxval+=u->lc->rmax;
  22.     if(u->rc && u->rc->lmax>0) u->maxval+=u->rc->lmax;
  23.     if(u->lc) {
  24.     u->size+=u->lc->size;
  25.     u->sum+=u->lc->sum;
  26.     u->maxval=max(u->maxval,u->lc->maxval);
  27.     }
  28.     if(u->rc) {
  29.     u->size+=u->rc->size;
  30.     u->sum+=u->rc->sum;
  31.     u->maxval=max(u->maxval,u->rc->maxval);
  32.     }
  33.     if(u->lc==NULL && u->rc==NULL) {
  34.     u->lmax=u->rmax=u->val;
  35.     }
  36.     else if(u->lc==NULL) {
  37.     u->lmax=max(u->val,u->val+u->rc->lmax);
  38.     u->rmax=max(u->rc->rmax,u->rc->sum+u->val);
  39.     }
  40.     else if(u->rc==NULL) {
  41.     u->rmax=max(u->val,u->val+u->lc->rmax);
  42.     u->lmax=max(u->lc->lmax,u->lc->sum+u->val);
  43.     }
  44.     else {
  45.     u->lmax=max(u->lc->sum+u->val+u->rc->lmax,u->lc->sum+u->val);
  46.     u->lmax=max(u->lmax,u->lc->lmax);
  47.     u->rmax=max(u->rc->sum+u->val+u->lc->rmax,u->rc->sum+u->val);
  48.     u->rmax=max(u->rmax,u->rc->rmax);
  49.     }
  50. }
  51. void pushdown(node *u) {
  52.     if(u->rev) {
  53.     swap(u->lc,u->rc);
  54.     swap(u->lmax,u->rmax);
  55.     if(u->lc) {u->lc->rev^=1;}
  56.     if(u->rc) {u->rc->rev^=1;}
  57.     u->rev=0;
  58.     }
  59.     if(u->iscover) {
  60.     u->sum=u->size*u->cover;
  61.     u->val=u->cover;
  62.     u->lmax=max(u->val,u->sum);
  63.     u->rmax=max(u->val,u->sum);
  64.     u->maxval=max(u->val,u->sum);
  65.     u->iscover=0;
  66.     if(u->lc) {u->lc->iscover=1;u->lc->cover=u->cover;}
  67.     if(u->rc) {u->rc->iscover=1;u->rc->cover=u->cover;}
  68.     }
  69. }
  71. node *findpos(node *u,int s) {
  73.     pushdown(u);
  74.     if(u->lc) pushdown(u->lc);
  75.     if(u->rc) pushdown(u->rc);
  76.     int k=(u->lc!=NULL) ? u->lc->size : 0;
  77.     node *res;
  78.     if(k+1==s) res=u;
  79.     else if(k>=s) {
  80.     res=findpos(u->lc,s);
  81.     }
  82.     else {
  83.     res=findpos(u->rc,s-k-1);
  84.     }
  85.     return res;
  86. }
  87. void rotate(node *u) {
  88.     node *v = u->fa,*w= v->fa;
  89.     node *b= (u==v->lc) ? u->rc : u->lc;
  90.     u->fa=w;v->fa=u;
  91.     if(b) b->fa=v;
  92.     if(w) {(v==w->lc ? w->lc : w->rc) = u;}
  93.     if(u==v->lc) {v->lc = b;u->rc = v;}
  94.     else {v->rc = b;u->lc = v;}
  95.     update(v);
  96. }
  97. int which(node *u) {
  98.     return u->fa->rc == u;
  99. }
  100. void splay(node  *u,node *tar) {
  102.     while(u->fa!=tar) {
  103.     if(u->fa->fa!=tar) {
  104.         if(which(u->fa) == which(u)) rotate(u->fa);
  105.         else rotate(u);
  106.     }
  107.     rotate(u);
  108.     }
  109.     update(u);
  110.     if(tar==NULL) root=u;
  111. }
  112. node *build(int l,int r) {
  113.     if(l>r) return NULL;
  114.     node *res=new node;
  115.     res->fa=res->lc=res->rc=NULL;
  116.     res->rev=res->iscover=0;
  117.     res->size=1;
  118.     if(l==r) {
  119.     res->val=a[l];
  120.     update(res);
  121.     return res;
  122.     }
  123.     int mid=(l+r)>>1;
  124.     res->val=a[mid+1];
  125.     res->lc=build(l,mid);
  126.     res->rc=build(mid+2,r);
  127.     if(res->lc) res->lc->fa=res;
  128.     if(res->rc) res->rc->fa=res;
  129.     update(res);
  130.     return res;
  131. }
  132. void Insert() {
  133.     int pos,tot;
  134.     scanf("%d%d",&pos,&tot);
  135.     siji(i,1,tot) scanf("%d",&a[i]);
  136.     node *pre=findpos(root,pos+1),*suf=findpos(root,pos+2);
  137.     splay(pre,NULL);
  138.     splay(suf,pre);
  139.     if(suf==NULL) {puts("QAQ");return;}
  140.     suf->lc=build(1,tot);
  141.     if(suf->lc) suf->lc->fa=suf;
  142.     update(suf);update(pre);
  143. }
  144. void dfs_delete(node *u) {
  145.     if(u==NULL) return;
  146.     dfs_delete(u->lc);
  147.     dfs_delete(u->rc);
  148.     delete u;
  149. }
  150. void Delete() {
  151.     int pos,tot;
  152.     scanf("%d%d",&pos,&tot);
  153.     node *pre=findpos(root,pos),*suf=findpos(root,pos+tot+1);
  154.     splay(pre,NULL);
  155.     splay(suf,pre);
  156.     if(suf==NULL) {puts("QAQ");return;}
  157.     dfs_delete(suf->lc);
  158.     suf->lc=NULL;
  159.     update(suf);update(pre);
  160. }
  161. void Make_same() {
  162.     int pos,tot,c;
  163.     scanf("%d%d%d",&pos,&tot,&c);
  164.     node *pre=findpos(root,pos),*suf=findpos(root,pos+tot+1);
  165.     splay(pre,NULL);
  166.     splay(suf,pre);
  167.     if(suf->lc) {
  168.     suf->lc->iscover=1;
  169.     suf->lc->cover=c;
  170.     pushdown(suf->lc);
  171.     }
  172.     update(suf);update(pre);
  173. }
  174. void Reverse() {
  175.     int pos,tot;
  176.     scanf("%d%d",&pos,&tot);
  177.     node *pre=findpos(root,pos),*suf=findpos(root,pos+1+tot);
  178.     splay(pre,NULL);
  179.     splay(suf,pre);
  180.     if(suf->lc) {
  181.     suf->lc->rev^=1;
  182.     pushdown(suf->lc);
  183.     }
  184.     update(suf);update(pre);
  185. }
  186. void Get_sum() {
  187.     int pos,tot;
  189.     scanf("%d%d",&pos,&tot);
  190.     node *pre=findpos(root,pos),*suf=findpos(root,pos+1+tot);
  191.     splay(pre,NULL);
  192.     splay(suf,pre);
  194.     if(suf->lc) {
  195.     printf("%d\n",suf->lc->sum);
  196.     }
  197.     else {puts("0");}
  198. }
  199. void Max_sum() {
  200.     if(root==NULL) {puts("QAQ");return;}
  201.     pushdown(root);
  202.     printf("%d\n",root->maxval);
  203. }
  204. int main() {
  205.     scanf("%d%d",&n,&m);
  206.     a[1]=-100000;a[n+2]=-1000000;
  207.     siji(i,2,n+1) {
  208.     scanf("%d",&a[i]);
  209.     }
  210.     root=build(1,n+2);
  211.     siji(i,1,m) {
  212.     scanf("%s",s+1);
  213.     if(s[1]=='I') {
  214.         Insert();
  215.     }
  216.     else if(s[1]=='D') {
  217.         Delete();
  218.     }
  219.     else if(s[3]=='K'){
  220.         Make_same();
  221.     }
  222.     else if(s[1]=='R') {
  223.         Reverse();
  224.     }
  225.     else if(s[1]=='G') {
  226.         Get_sum();
  227.     }
  228.     else {
  229.         Max_sum();
  230.     }
  231.     }
  232.     return 0;
  233. }

主席树

K-th Number

Description

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.
That is, given an array a[1...n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: "What would be the k-th number in a[i...j] segment, if this segment was sorted?"
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.

Input

The first line of the input file contains n --- the size of the array, and m --- the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000).
The second line contains n different integer numbers not exceeding 109 by their absolute values --- the array for which the answers should be given.
The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).

Output

For each question output the answer to it --- the k-th number in sorted a[i...j] segment.

Sample Input

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

Sample Output

5
6
3

Hint

This problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed.

题解

这是主席树的板子题
主席树需要先把所有的数离散化，然后将线段树建在一个值域上
插入每个点，如果在左儿子就新建一个左儿子，如果在右儿子就新建一个右儿子，节点中维护的是这个值域里的数有几个
查询的时候查询一个区间的[l,r],查找以l-1和r为根的树，这个区间所含数的个数是r所在的节点的sum减去l-1所在节点的sum，我们查左儿子的大小，如果左儿子大于等于k就去左儿子，否则去右儿子

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  6. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  7. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  8. #define MAXN 100005
  9. //#define ivorysi
  10. using namespace std;
  11. typedef long long ll;
  12. int n,q,m;
  13. int a[MAXN],b[MAXN];
  14. struct node {
  15.     int lc,rc,sum;
  16. }tr[MAXN*20];
  17. int root[MAXN],nodecnt;
  18. void dist_init() {
  19.     memcpy(b,a,sizeof(a));
  20.     sort(b+1,b+n+1);
  21.     m=unique(b+1,b+n+1)-b-1;
  22.     siji(i,1,n) {
  23.     a[i]=lower_bound(b+1,b+m+1,a[i])-b;
  24.     }
  25. }
  26. void Insert(int y,int &x,int l,int r,int val) {
  27.     tr[x = ++nodecnt]=tr[y];
  28.     tr[x].sum++;
  29.     if(l==r) return;
  30.     int mid=(l+r)>>1;
  31.     if(val<=mid) 
  32.     Insert(tr[y].lc,tr[x].lc,l,mid,val);
  33.     else 
  34.     Insert(tr[y].rc,tr[x].rc,mid+1,r,val);
  35. }
  36. int Query(int nl,int nr,int l,int r,int k) {
  37.     if(l==r) return l;
  38.     int delta=tr[tr[nr].lc].sum-tr[tr[nl].lc].sum;
  39.     int mid=(l+r)>>1;
  40.     if(k<=delta) 
  41.     return Query(tr[nl].lc,tr[nr].lc,l,mid,k);
  42.     else 
  43.     return Query(tr[nl].rc,tr[nr].rc,mid+1,r,k-delta);
  44. }
  45. void tree_init() {
  46.     siji(i,1,n) 
  47.     Insert(root[i-1],root[i],1,m,a[i]);
  48. }
  49. int main() {
  50. #ifdef ivorysi
  51.     freopen("f1.in","r",stdin);
  52. #endif
  53.     scanf("%d%d",&n,&q);
  54.     siji(i,1,n) scanf("%d",&a[i]);
  55.     dist_init();
  56.     tree_init();
  57.     int l,r,k;
  58.     siji(i,1,q) {
  59.     scanf("%d%d%d",&l,&r,&k);
  60.     printf("%d\n",b[Query(root[l-1],root[r],1,m,k)]);
  61.     }
  62.     return 0;
  63. }

BZOJ 3932: [CQOI2015]任务查询系统

Description

最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的
任务用三元组(Si,Ei,Pi)描述，(Si,Ei,Pi)表示任务从第Si秒开始，在第Ei秒后结束（第Si秒和Ei秒任务也在运行
），其优先级为Pi。同一时间可能有多个任务同时执行，它们的优先级可能相同，也可能不同。调度系统会经常向
查询系统询问，第Xi秒正在运行的任务中，优先级最小的Ki个任务（即将任务按照优先级从小到大排序后取前Ki个
）的优先级之和是多少。特别的，如果Ki大于第Xi秒正在运行的任务总数，则直接回答第Xi秒正在运行的任务优先
级之和。上述所有参数均为整数，时间的范围在1到n之间（包含1和n）。

Input

输入文件第一行包含两个空格分开的正整数m和n，分别表示任务总数和时间范围。接下来m行，每行包含三个空格
分开的正整数Si、Ei和Pi(Si≤Ei)，描述一个任务。接下来n行，每行包含四个空格分开的整数Xi、Ai、Bi和Ci，
描述一次查询。查询的参数Ki需要由公式 Ki=1+(Ai*Pre+Bi) mod Ci计算得到。其中Pre表示上一次查询的结果，
对于第一次查询，Pre=1。

Output

输出共n行，每行一个整数，表示查询结果。

Sample Input

4 3
1 2 6
2 3 3
1 3 2
3 3 4
3 1 3 2
1 1 3 4
2 2 4 3

Sample Output

2
8
11

HINT

样例解释

K1 = (1*1+3)%2+1 = 1
K2 = (1*2+3)%4+1 = 2
K3 = (2*8+4)%3+1 = 3
对于100%的数据，1≤m,n,Si,Ei,Ci≤100000，0≤Ai,Bi≤100000，1≤Pi≤10000000，Xi为1到n的一个排列

题解

这道题我们建主席树，按时间建值域线段树，维护两个值，一个是节点大小，一个是节点上的值
然而我rc写成lc了！！！！
我们建两个vector，一个是起始点，我们不断地加入，一个是终止点，我们不断地删除
查询的时候直接去树里找，然后如果k大于整个左区间就加上整个区间的总和

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <vector>
  6. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  7. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  8. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  9. #define MAXN 100005
  10. //#define ivorysi
  11. using namespace std;
  12. typedef long long ll;
  13. struct node {
  14.     int lc,rc,size;
  15.     ll val;
  16. }tr[MAXN*60];
  17. int root[MAXN],nodecnt;
  18. int m,n,tot;
  19. ll num[MAXN];
  20. vector<ll> st[MAXN],ed[MAXN];
  21. void Insert(int y,int &x,int l,int r,int id,int on) {
  22.     tr[x = ++nodecnt]=tr[y];
  23.     tr[x].size+=on;
  24.     tr[x].val+=1LL*on*num[id];
  25.     if(l==r) return;
  26.     int mid=(l+r)>>1;
  27.     if(id<=mid) {
  28.     Insert(tr[y].lc,tr[x].lc,l,mid,id,on);
  29.     }
  30.     else {
  31.     Insert(tr[y].rc,tr[x].rc,mid+1,r,id,on);
  32.     }
  33. }
  34. ll Query(int x,int l,int r,int k) {
  35.     if(tr[x].size<=k) return tr[x].val;
  36.     if(l==r) return k*num[l];
  37.     int mid=(l+r)>>1;
  38.     int delta=tr[tr[x].lc].size;
  39.     if(delta>=k) {
  40.     return Query(tr[x].lc,l,mid,k);
  41.     }
  42.     else {
  43.     return tr[tr[x].lc].val+Query(tr[x].rc,mid+1,r,k-delta);
  44.     }
  45. }
  46. int main() {
  47. #ifdef ivorysi
  48.     freopen("f1.in","r",stdin);
  49. #endif
  50.     scanf("%d%d",&m,&n);
  51.     int s,e,p;
  52.     siji(i,1,m) {
  53.     scanf("%d%d%d",&s,&e,&p);
  54.     st[s].push_back(p);
  55.     ed[e+1].push_back(p);
  56.     num[i]=p;
  57.     }
  58.     sort(num+1,num+m+1);
  59.     tot=unique(num+1,num+m+1)-num-1;
  60.     siji(i,1,n) {
  61.     int s=st[i].size();
  62.     root[i]=root[i-1];
  63.     xiaosiji(j,0,s) {
  64.         int id=lower_bound(num+1,num+tot+1,st[i][j])-num;
  65.         int x=root[i];
  66.         Insert(x,root[i],1,tot,id,1);
  67.     }
  68.     s=ed[i].size();
  69.     xiaosiji(j,0,s) {
  70.         int id=lower_bound(num+1,num+tot+1,ed[i][j])-num;
  71.         int x=root[i];
  72.         Insert(x,root[i],1,tot,id,-1);
  73.     }
  74.     }
  75.     ll pr=1;
  76.     int a,b,c,k,x;
  77.     siji(i,1,n) {
  78.     scanf("%d%d%d%d",&x,&a,&b,&c);
  79.     k=1LL*(1LL*a*pr+b)%c+1;
  80.     pr = Query(root[x],1,tot,k);
  81.     printf("%lld\n",pr);
  82.     }
  83.     return 0;
  84. }

BZOJ 1901: Zju2112 Dynamic Rankings

Description

给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1
],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改
变后的a继续回答上面的问题。

Input

第一行有两个正整数n(1≤n≤10000)，m(1≤m≤10000)。
分别表示序列的长度和指令的个数。
第二行有n个数，表示a[1],a[2]……a[n]，这些数都小于10^9。
接下来的m行描述每条指令
每行的格式是下面两种格式中的一种。
Q i j k 或者 C i t
Q i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1）
表示询问指令，询问a[i]，a[i+1]……a[j]中第k小的数。
C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改变成为t
m,n≤10000

Output

对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。

Sample Input

5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

Sample Output

3
6

题解

这道题是带修改的主席树
我们可以用树状数组来维护这个东西
log n个点一起向下爬树
为什么开200倍的点都RE，严重怀疑n是10^5

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <vector>
  6. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  7. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  8. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  9. #define MAXN 100005
  10. //#define ivorysi
  11. using namespace std;
  12. typedef long long ll;
  13. struct node {
  14.     int lc,rc,size;
  15. }tr[MAXN*40];
  16. struct date {
  17.     int op,l,r,k;
  18.     int pos,t;
  19. }p[MAXN];
  20. int n,m,nodecnt,root[MAXN],crt[2][MAXN],tot,num[MAXN*2];
  21. int a[MAXN],now;
  22. char s[10];
  23. inline int lowbit(int x) {return x&(-x);}
  24. void Insert(int y,int &x,int l,int r,int on,int val) {
  25.     tr[x=++nodecnt]=tr[y];
  26.     tr[x].size+=on;
  27.     if(l==r) return;
  28.     int mid=(l+r)>>1;
  29.     if(val<=mid) {
  30.         Insert(tr[y].lc,tr[x].lc,l,mid,on,val);
  31.     }
  32.     else {
  33.         Insert(tr[y].rc,tr[x].rc,mid+1,r,on,val);
  34.     }
  35. }
  36. void add(int x,int on,int val) {
  37.     for(int i=x;i<=n;i+=lowbit(i)) Insert(root[i],root[i],1,tot,on,val);
  38. } 
  39. int getsum(int x) {
  40.     int res=0;
  41.     for(int i=x;i>=1;i-=lowbit(i)) res+=tr[tr[crt[now][i]].lc].size;
  42.     return res;
  43. }
  44. int query(int ql,int qr,int k) {
  45.     now=0;
  46.     for(int i=qr;i>=1;i-=lowbit(i)) crt[now][i]=root[i];
  47.     for(int i=ql;i>=1;i-=lowbit(i)) crt[now][i]=root[i];
  48.     int l=1,r=tot;
  49.     while(l<r) {
  50.         int delta=getsum(qr)-getsum(ql);
  51.         int mid=(l+r)>>1;
  52.         if(k<=delta) {
  53.             r=mid;
  54.             for(int i=qr;i>=1;i-=lowbit(i)) crt[now^1][i]=tr[crt[now][i]].lc;
  55.             for(int i=ql;i>=1;i-=lowbit(i)) crt[now^1][i]=tr[crt[now][i]].lc;
  56.         }
  57.         else {
  58.             k-=delta;
  59.             l=mid+1;
  60.             for(int i=qr;i>=1;i-=lowbit(i)) crt[now^1][i]=tr[crt[now][i]].rc;
  61.             for(int i=ql;i>=1;i-=lowbit(i)) crt[now^1][i]=tr[crt[now][i]].rc;
  62.         }
  63.         now^=1;
  64.     }
  65.     return num[l];
  66. }   
  67. int main() {
  68. #ifdef ivorysi
  69.     freopen("f1.in","r",stdin);
  70. #endif
  71.     scanf("%d%d",&n,&m);
  72.     siji(i,1,n) {
  73.         scanf("%d",&a[i]);
  74.         num[i]=a[i];
  75.     }
  76.     siji(i,1,m) {
  77.         scanf("%s",s+1);
  78.         if(s[1]=='Q') {
  79.             p[i].op=1;
  80.             scanf("%d%d%d",&p[i].l,&p[i].r,&p[i].k);
  81.         }
  82.         else {
  83.             p[i].op=2;
  84.             scanf("%d%d",&p[i].pos,&p[i].t);
  85.             num[i+n]=p[i].t;
  86.         }
  87.     }
  88.     sort(num+1,num+n+m+1);
  89.     tot=unique(num+1,num+n+m+1)-num-1;
  90.     siji(i,1,n)  {
  91.         int id=lower_bound(num+1,num+tot+1,a[i])-num;
  92.         add(i,1,id);
  93.     }
  94.     siji(i,1,m) {
  95.         if(p[i].op==1) {
  96.             printf("%d\n",query(p[i].l-1,p[i].r,p[i].k));
  97.         }
  98.         else {
  99.             int id=lower_bound(num+1,num+tot+1,a[p[i].pos])-num;
  100.             add(p[i].pos,-1,id);
  101.             id=lower_bound(num+1,num+tot+1,p[i].t)-num;
  102.             add(p[i].pos,1,id);
  103.             a[p[i].pos]=p[i].t;
  104.         }
  105.     }
  106.     return 0;
  107. }

BZOJ 2223

题面大意：给出n个数和这些数的范围（10000）以内
然后给出m个询问[l,r]区间内有没有一个数的出现次数大于(r-l+1)/2

题解

因为我们建的是值域线段树，所以如果有一个区间里的数字个数大于（r-l+1)/2那么必然，这里可能有我们要找的数，如果没有的话，那就是没有解，如果正好找到单个区间里数字个数大于(r-l+1)/2，那么就是我们想要的数字
建好主席树之后跑就行

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <vector>
  6. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  7. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  8. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  9. #define MAXN 300005
  10. //#define ivorysi
  11. using namespace std;
  12. typedef long long ll;
  13. struct node {
  14.     int lc,rc,size;
  15. }tr[MAXN*20];
  16. int root[MAXN],nodecnt,n,m,lim,a[MAXN],pos;
  17. void Insert(int y,int &x,int l,int r,int val) {
  18.     tr[x=++nodecnt]=tr[y];
  19.     ++tr[x].size;
  20.     if(l==r) return ;
  21.     int mid=(l+r)>>1;
  22.     if(val<=mid) Insert(tr[y].lc,tr[x].lc,l,mid,val);
  23.     else Insert(tr[y].rc,tr[x].rc,mid+1,r,val);
  24. }
  25. bool Query(int nl,int nr,int l,int r,int x) {
  26.     if(l==r) {pos=l;return 1;}
  27.     int delta_left=tr[tr[nr].lc].size-tr[tr[nl].lc].size;
  28.     int delta_right=tr[tr[nr].rc].size-tr[tr[nl].rc].size;
  29.     int mid=(l+r)>>1;
  30.     if(delta_left > x) return Query(tr[nl].lc,tr[nr].lc,l,mid,x);
  31.     if(delta_right > x) return Query(tr[nl].rc,tr[nr].rc,mid+1,r,x);
  32.     return 0;
  33. }
  34. int main() {
  35. #ifdef ivorysi
  36.     freopen("f1.in","r",stdin);
  37. #endif
  38.     scanf("%d%d",&n,&lim);
  39.     siji(i,1,n) {
  40.     scanf("%d",&a[i]);
  41.     Insert(root[i-1],root[i],1,lim,a[i]);
  42.     }
  43.     int l,r;
  44.     scanf("%d",&m);
  45.     siji(i,1,m) {
  46.     scanf("%d%d",&l,&r);
  47.     if(Query(root[l-1],root[r],1,lim,(r-l+1)/2)) {
  48.         printf("yes %d\n",pos);
  49.     }
  50.     else {
  51.         printf("no\n");
  52.     }
  53.     }
  54.     return 0;
  55. }

BZOJ 2588: Spoj 10628. Count on a tree

Description

给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。

Input

第一行两个整数N,M。
第二行有N个整数，其中第i个整数表示点i的权值。
后面N-1行每行两个整数(x,y)，表示点x到点y有一条边。
最后M行每行两个整数(u,v,k)，表示一组询问。

Output

M行，表示每个询问的答案。最后一个询问不输出换行符

Sample Input

8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
0 5 2
10 5 3
11 5 4
110 8 2

Sample Output

2
8
9
105
7

题解

这道题又是强制在线……
我们的主席树的精髓在于，建一棵前缀的线段树
在树上我们也一样，我们可以建一棵根缀的线段树，我们每个节点的主席树从父亲更新就可以了
然后查询的时候找到lca，然后找到这条路径所表示的线段树（是两个线段树的和），就可以像普通第k大那样查询了

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <vector>
  6. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  7. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  8. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  9. #define MAXN 100005
  10. //#define ivorysi
  11. using namespace std;
  12. typedef long long ll;
  13. struct node {
  14.     int lc,rc,size;
  15. }tr[MAXN*20];
  16. struct data {
  17.     int next,to;
  18. }edge[MAXN*4];
  19. int root[MAXN],nodecnt,n,m,val[MAXN],pos,num[MAXN],tot;
  20. int head[MAXN],sumedge,fa[MAXN][25],dep[MAXN];
  21. void add(int u,int v) {
  22.     edge[++sumedge].to=v;
  23.     edge[sumedge].next=head[u];
  24.     head[u]=sumedge;
  25. }
  26. void addtwo(int u,int v) {
  27.     add(u,v);
  28.     add(v,u);
  29. }
  30. void Insert(int y,int &x,int l,int r,int v) {
  31.     tr[x=++nodecnt]=tr[y];
  32.     ++tr[x].size;
  33.     if(l==r) return;
  34.     int mid=(l+r)>>1;
  35.     if(v<=mid) {
  36.     Insert(tr[y].lc,tr[x].lc,l,mid,v);
  37.     }
  38.     else {
  39.     Insert(tr[y].rc,tr[x].rc,mid+1,r,v);
  40.     }
  41. }
  42. void dfs(int u) {
  43.     int id=lower_bound(num+1,num+tot+1,val[u])-num;
  44.     Insert(root[fa[u][0]],root[u],1,tot,id);
  45.     for(int i=head[u];i;i=edge[i].next) {
  46.     int v=edge[i].to;
  47.     if(v!=fa[u][0]) {
  48.         dep[v]=dep[u]+1;
  49.         fa[v][0]=u;
  50.         dfs(v);
  51.     }
  52.     }
  53. }
  54. int lca(int a,int b) {
  55.     if(dep[a]<dep[b]) swap(a,b);
  56.     int l=17;
  57.     while(dep[a]>=dep[b] && l>=0) {
  58.     if(dep[fa[a][l]]>=dep[b]) {
  59.         a=fa[a][l];
  60.     }
  61.     --l;
  62.     }
  63.     if(a==b) return a;
  64.     l=17;
  65.     while(fa[a][0]!=fa[b][0]) {
  66.     if(fa[a][l]!=fa[b][l]) {
  67.         a=fa[a][l];
  68.         b=fa[b][l];
  69.     }
  70.     --l;
  71.     }
  72.     return fa[a][0];
  73. }
  74. int getsum(int a,int b) {
  75.     return tr[tr[a].lc].size-tr[tr[b].lc].size;
  76. }
  77. int Query(int left,int left_st,int right,int right_st,int k) {
  78.     int l=1,r=tot;
  79.     while(l<r) {
  80.     int delta=getsum(left,left_st)+getsum(right,right_st);
  81.     int mid=(l+r)>>1;
  82.     if(delta>=k) {
  83.         r=mid;
  84.         left=tr[left].lc;
  85.         left_st=tr[left_st].lc;
  86.         right=tr[right].lc;
  87.         right_st=tr[right_st].lc;
  88.     }
  89.     else {
  90.         l=mid+1;
  91.         k-=delta;
  92.         left=tr[left].rc;
  93.         left_st=tr[left_st].rc;
  94.         right=tr[right].rc;
  95.         right_st=tr[right_st].rc;
  96.     }
  97.     }
  98.     if(l==r) return num[l];
  99. }
  100. int main() {
  101. #ifdef ivorysi
  102.     freopen("f1.in","r",stdin);
  103. #endif
  104.     scanf("%d%d",&n,&m);
  105.     siji(i,1,n) {
  106.     scanf("%d",&val[i]);
  107.     num[i]=val[i];
  108.     }
  109.     int u,v,k;
  110.     xiaosiji(i,1,n) {
  111.     scanf("%d%d",&u,&v);
  112.     addtwo(u,v);
  113.     }
  114.     sort(num+1,num+n+1);
  115.     tot=unique(num+1,num+n+1)-num-1;
  116.     dep[1]=1;
  117.     dfs(1);
  118.     int lastans=0;
  119.     siji(j,1,17) {
  120.     siji(i,1,n) {
  121.         fa[i][j]=fa[fa[i][j-1]][j-1];
  122.     }
  123.     }
  125.     siji(i,1,m) {
  126.     scanf("%d%d%d",&u,&v,&k);
  127.     u^=lastans;
  128.     int f=lca(u,v);
  129.     lastans=Query(root[u],root[f],root[v],root[fa[f][0]],k);
  130.     printf("%d",lastans);
  131.     if(i!=m) putchar('\n');
  132.     }
  133.     return 0;
  134. }

BZOJ 2653: middle

Description

一个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号,除法取下整。给你一个
长度为n的序列s。回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。
其中a

Input

第一行序列长度n。接下来n行按顺序给出a中的数。
接下来一行Q。然后Q行每行a,b,c,d，我们令上个询问的答案是
x(如果这是第一个询问则x=0)。
令数组q={(a+x)%n,(b+x)%n,(c+x)%n,(d+x)%n}。
将q从小到大排序之后，令真正的
要询问的a=q[0],b=q[1],c=q[2],d=q[3]。　　
输入保证满足条件。
第一行所谓“排过序”指的是从大到小排序！

Output

Q行依次给出询问的答案。

Sample Input

5
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0

Sample Output

271451044
271451044
969056313

HINT

0,...,19:n<=20000,Q<=25000

题解

这道题的思路很妙
我一直觉得是左子树要是稍小一点就可以往右子树走，然而我觉得中间情况不好处理
但是我们如果已知我们想要的中位数是什么，把小于等于这个数的数设成1，把大于这个数的设成-1，如果一个子段和大于等于0就证明这个中位数可以取到
我们发现[b,c]这段必须取，我们需要[a,b)后缀最大值，(c,d]前缀最大值
这个怎么维护呢，我们把值排序，每次从前一个转移过来，root[i]表示第i大的值的线段树
可以不用离散化，因为数比较少，省的太麻烦
维护一下线段树的和，左最大值，右最大值

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <vector>
  6. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  7. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  8. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  9. #define MAXN 100005
  10. //#define ivorysi
  11. using namespace std;
  12. typedef long long ll;
  13. int n,Q,b[6];
  14. struct node{
  15.     int lc,rc,sum;
  16.     int lmax,rmax;
  17. }tr[MAXN*20];
  18. int root[MAXN],nodecnt;
  19. struct data {
  20.     int val,pos;
  21.     bool operator < (const data &rhs) const{
  22.     return val<rhs.val;
  23.     }
  24. }a[MAXN];
  25. void update(int u) {
  26.     tr[u].sum=tr[tr[u].lc].sum+tr[tr[u].rc].sum;
  27.     tr[u].lmax=max(tr[tr[u].lc].lmax,tr[tr[u].lc].sum+tr[tr[u].rc].lmax);
  28.     tr[u].rmax=max(tr[tr[u].rc].rmax,tr[tr[u].rc].sum+tr[tr[u].lc].rmax);
  29. }
  30. void Insert(int y,int &x,int l,int r,int val,int on) {
  31.     tr[x=++nodecnt]=tr[y];
  32.     if(l==r) {
  33.     tr[x].sum=on;
  34.     tr[x].lmax=tr[x].rmax=max(on,0);
  35.     return;
  36.     }
  37.     int mid=(l+r)>>1;
  38.     if(mid>=val) {
  39.     Insert(tr[y].lc,tr[x].lc,l,mid,val,on);
  40.     }
  41.     else {
  42.     Insert(tr[y].rc,tr[x].rc,mid+1,r,val,on);
  43.     }
  44.     update(x);
  45. }
  46. void build(int u,int l,int r) {
  47.     if(l==r) {
  48.     tr[u].lmax=tr[u].rmax=tr[u].sum=1;
  49.     return;
  50.     }
  51.     int mid=(l+r)>>1;
  52.     build(tr[u].lc=++nodecnt,l,mid);
  53.     build(tr[u].rc=++nodecnt,mid+1,r);
  54.     update(u);
  55. }
  56. int query_sum(int u,int l,int r,int ql,int qr) {
  57.     if(l==ql && r==qr) {
  58.     return tr[u].sum;
  59.     }
  60.     int mid=(l+r)>>1;
  61.     if(qr<=mid) {
  62.     return query_sum(tr[u].lc,l,mid,ql,qr);
  63.     }
  64.     else if(ql>mid) {
  65.     return query_sum(tr[u].rc,mid+1,r,ql,qr);
  66.     }
  67.     else {
  68.     return query_sum(tr[u].lc,l,mid,ql,mid)+query_sum(tr[u].rc,mid+1,r,mid+1,qr);
  69.     }
  70. }
  71. int query_lmax(int u,int l,int r,int ql,int qr) {
  72.     if(l==ql && r==qr) {
  73.     return tr[u].lmax;
  74.     }
  75.     int mid=(l+r)>>1;
  76.     if(qr<=mid) {
  77.     return query_lmax(tr[u].lc,l,mid,ql,qr);
  78.     }
  79.     else if(ql>mid) {
  80.     return query_lmax(tr[u].rc,mid+1,r,ql,qr);
  81.     }
  82.     else {
  83.     return max(query_lmax(tr[u].lc,l,mid,ql,mid),query_sum(tr[u].lc,l,mid,ql,mid)+query_lmax(tr[u].rc,mid+1,r,mid+1,qr));
  84.     }
  85. }
  86. int query_rmax(int u,int l,int r,int ql,int qr) {
  87.     if(l==ql && r==qr) {
  88.     return tr[u].rmax;
  89.     }
  90.     int mid=(l+r)>>1;
  91.     if(qr<=mid) {
  92.     return query_rmax(tr[u].lc,l,mid,ql,qr);
  93.     }
  94.     else if(ql>mid) {
  95.     return query_rmax(tr[u].rc,mid+1,r,ql,qr);
  96.     }
  97.     else {
  98.     return max(query_rmax(tr[u].rc,mid+1,r,mid+1,qr),query_sum(tr[u].rc,mid+1,r,mid+1,qr)+query_rmax(tr[u].lc,l,mid,ql,mid));
  99.     }
  100. }
  101. bool check(int k,int a,int b,int c,int d) {
  102.     int tmp=query_sum(k,1,n,b,c);
  103.     if(a<=b-1)tmp+=query_rmax(k,1,n,a,b-1);
  104.     if(c+1<=d)tmp+=query_lmax(k,1,n,c+1,d);
  105.     return tmp>=0;
  106. }
  107. int main() {
  108. #ifdef ivorysi
  109.     freopen("f1.in","r",stdin);
  110. #endif
  111.     scanf("%d",&n);
  112.     siji(i,1,n) {
  113.     scanf("%d",&a[i].val);
  114.     a[i].pos=i;
  115.     }
  116.     sort(a+1,a+n+1);
  117.     build(root[1]=++nodecnt,1,n);
  118.     siji(i,2,n) {
  119.     Insert(root[i-1],root[i],1,n,a[i-1].pos,-1);
  120.     }
  121.     scanf("%d",&Q);
  122.     int lastans=0;
  123.     siji(i,1,Q) {
  124.     scanf("%d%d%d%d",&b[0],&b[1],&b[2],&b[3]);
  125.     siji(j,0,3) b[j]=(b[j]%n+lastans)%n+1;
  126.     sort(b,b+4);
  127.     int l=1,r=n;
  128.     while(l<r) {
  129.         int mid=(l+r+1)>>1;
  130.         if(check(root[mid],b[0],b[1],b[2],b[3])) {
  131.         l=mid;
  132.         }
  133.         else {
  134.         r=mid-1;
  135.         }
  136.     }
  137.     printf("%d\n",a[l].val);
  138.     lastans=a[l].val%n;
  139.     }
  140.     return 0;
  141. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注