如果是1~n 个数 那么我们知道线段树 最后一层 一定是n个结点!
那么 可得线段树 最多的结点数为 2^(log2(n)+1)-1 或者 2*n-1个
单点更新
HDU1754
//9596209 2013-11-16 12:13:35 Accepted 1754 531MS 7184K 1579 B #include <iostream> #include<cstdio> using namespace std; #define MAX 200002 int val[MAX]; struct Node { int left,right,max; }tree[3*MAX]; int max(int a,int b) { return a>b?a:b; } int creat(int root,int left,int right) { tree[root].left=left; tree[root].right=right; if(left==right) return tree[root].max=val[left]; int a,b,mid; mid=(right-left)/2+left; a=creat(2*root,left,mid); b=creat(2*root+1,mid+1,right); return tree[root].max=max(a,b); } int calculate(int root,int left,int right) { if(tree[root].left>right || tree[root].right<left)/**两区间相离,就返回0**/ return 0; if(tree[root].left>=left&&tree[root].right<=right)/**区间在所求区间内部,就返回这个区间的最大值**/ return tree[root].max; int a,b; a=calculate(2*root,left,right); b=calculate(2*root+1,left,right); return max(a,b); } int updata(int root,int pos,int v) { if(pos<tree[root].left||pos>tree[root].right) return tree[root].max; if(pos==tree[root].left&&pos==tree[root].right) return tree[root].max=v; int a,b; a=updata(root*2,pos,v); b=updata(root*2+1,pos,v); return tree[root].max=max(a,b); } int main() { int n,m; while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=n;i++) scanf("%d",&val[i]); creat(1,1,n); for(int i=1;i<=m;i++) { char op; int x,y; scanf("\n%c%d%d",&op,&x,&y); if(op=='Q') printf("%d\n",calculate(1,x,y)); else updata(1,x,y); } } return 0; }
HDU1698
修改区间为定值
//9616564 2013-11-18 20:15:24 Accepted 1698 843MS/906MS 4764K 1995 B #include <iostream> #include<cstdio> using namespace std; #define MAX 100001 int val[MAX]; struct Node { int left,right; int mark; int total; }tree[3*MAX]; int creat(int root,int left,int right) { tree[root].left=left; tree[root].right=right; tree[root].mark=0; if(left==right) return tree[root].total=val[left]; int mid=(right+left)/2; return tree[root].total=creat(2*root,left,mid)+creat(2*root+1,mid+1,right); } void up_mark(int root) { if(tree[root].mark) { tree[root].total=tree[root].mark*(tree[root].right-tree[root].left+1); if(tree[root].left!=tree[root].right) tree[2*root].mark=tree[2*root+1].mark=tree[root].mark; tree[root].mark=0; } } int up_data(int root,int left,int right,int vol) { up_mark(root); if(tree[root].left>right || tree[root].right<left) return tree[root].total; if(tree[root].left>=left&&tree[root].right<=right) { tree[root].mark=vol; up_mark(root); return tree[root].total; //return tree[root].total=vol*(tree[root].right-tree[root].left+1); //843MS } return tree[root].total=up_data(2*root,left,right,vol)+up_data(2*root+1,left,right,vol); } int calculate(int root,int left,int right) { up_mark(root); if(tree[root].left>right || tree[root].right<left) return 0; if(tree[root].left>=left&&tree[root].right<=right) return tree[root].total; return tree[root].total=calculate(2*root,left,right)+calculate(2*root+1,left,right); } int main() { int t; int ces=1; scanf("%d",&t); while(t--) { int n,q,i; scanf("%d%d",&n,&q); for(i=1;i<=n;i++) val[i]=1; creat(1,1,n); int x,y,z; for(i=1;i<=q;i++) { scanf("%d%d%d",&x,&y,&z); up_data(1,x,y,z); } printf("Case %d: The total value of the hook is %d.\n",ces++,calculate(1,1,n)); } return 0; }
POJ3468
将区间的数加上某数
#include <iostream> #include<cstdio> using namespace std; #define MAX 100005 int val[MAX]; struct Node { int left,right; __int64 mark,total; }tree[MAX*3]; __int64 creat(int root,int left,int right) { tree[root].left=left; tree[root].right=right; tree[root].mark=0; if(left==right) return tree[root].total=val[left]; int mid=(right+left)/2; return tree[root].total=creat(2*root,left,mid)+creat(root*2+1,mid+1,right); } void up_mark(int root) { if(tree[root].mark) { tree[root].total+=tree[root].mark*(tree[root].right-tree[root].left+1); if(tree[root].left!=tree[root].right) { tree[2*root].mark+=tree[root].mark; tree[2*root+1].mark+=tree[root].mark; } tree[root].mark=0; } } __int64 up_data(int root,int left,int right,int vol) { up_mark(root); if(tree[root].left>right || tree[root].right<left) return tree[root].total; if(tree[root].left>=left&&tree[root].right<=right) { tree[root].mark=vol; up_mark(root); return tree[root].total; //return tree[root].total+=vol*(tree[root].right-tree[root].left+1); } return tree[root].total=up_data(2*root,left,right,vol)+up_data(2*root+1,left,right,vol); } __int64 calculate(int root,int left,int right) { up_mark(root); if(tree[root].left>right || tree[root].right<left) return 0; if(tree[root].left>=left&&tree[root].right<=right) return tree[root].total; return calculate(2*root,left,right)+calculate(2*root+1,left,right); } int main() { int n,q; while(~scanf("%d%d",&n,&q)) { for(int i=1;i<=n;i++) scanf("%d",&val[i]); creat(1,1,n); while(q--) { char op; scanf("\n%c",&op); if(op=='C') { int x,y,z; scanf("%d%d%d",&x,&y,&z); up_data(1,x,y,z); } else { int x,y; scanf("%d%d",&x,&y); printf("%I64d\n",calculate(1,x,y)); } } } return 0; }
区间染色问题
推荐 浙大ACM培训资料关于线段树的PPT
http://wenku.baidu.com/link?url=FWwB9gUJZZxWJuRNDCMcfBW8ebrEx6nRUJJkmqFcSRA_w1XOfv76lgrO-dLvzxvkh_LbXj05Ck1i5S9OBd0RbJBhLSj6lelePYmzSEi0r9W
POJ2528
题意:
有一些海报要贴墙上,按照先后顺序贴墙上,可以覆盖。问最后能看见几张海报(看见一部分也算)?、
分析:
这题就是:离散化+线段树 的水题。
染色一个区间就把这个区间 刷成一个值就好,最后遍历一遍整个区间看有几个不同的数,就有几张不同的海报。
//Accepted 1584K 125MS C++ 2835B #include <iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define MAXN 40000 int sub[MAXN]; struct node { int ll,rr,l,r; }qu[MAXN]; /**线段树部分**/ struct Node { int left,right; int mark; int total; }tree[3*MAXN]; int creat(int root,int left,int right) { tree[root].left=left; tree[root].right=right; tree[root].mark=0; if(left==right) return tree[root].total=-1; int mid=(right+left)/2; return tree[root].total=creat(2*root,left,mid)+creat(2*root+1,mid+1,right); } void up_mark(int root) { if(tree[root].mark) { tree[root].total=tree[root].mark*(tree[root].right-tree[root].left+1); if(tree[root].left!=tree[root].right) tree[2*root].mark=tree[2*root+1].mark=tree[root].mark; tree[root].mark=0; } } int up_data(int root,int left,int right,int vol) { up_mark(root); if(tree[root].left>right || tree[root].right<left) return tree[root].total; if(tree[root].left>=left&&tree[root].right<=right) { tree[root].mark=vol; up_mark(root); return tree[root].total; //return tree[root].total=vol*(tree[root].right-tree[root].left+1); //843MS } return tree[root].total=up_data(2*root,left,right,vol)+up_data(2*root+1,left,right,vol); } int calculate(int root,int left,int right) { up_mark(root); if(tree[root].left>right || tree[root].right<left) return 0; if(tree[root].left>=left&&tree[root].right<=right) return tree[root].total; return tree[root].total=calculate(2*root,left,right)+calculate(2*root+1,left,right); } /**线段树部分**/ int vis[MAXN]; int main() { int T;scanf("%d",&T); while(T--) { int n,num=0; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&qu[i].ll,&qu[i].rr); sub[num++] = qu[i].ll; sub[num++] = qu[i].rr; } sort(sub,sub+n*2); int X = unique(sub,sub+n*2)-sub; creat(1,1,X); /**建树**/ int color=0; for(int i=1;i<=n;i++) { qu[i].l = lower_bound(sub,sub+X,qu[i].ll)-sub+1; qu[i].r = lower_bound(sub,sub+X,qu[i].rr)-sub+1; color++; /**每个区间的颜色都不同!**/ up_data(1,qu[i].l,qu[i].r,color);/**覆盖区间**/ } int ans=0; memset(vis,0,sizeof(vis)); for(int i=1;i<=X;i++)/**遍历染色**/ { int t=calculate(1,i,i); //cout<<"----"<<t<<endl; if(t!=-1&& !vis[t]) { ans++; vis[t] = 1; } } printf("%d\n",ans); } return 0; } /** 10 5 30 1000 2 30 2 12 12 12000 1 2 **/
POJ2777
题意:一个长区间,初始全部染成颜色1,然后有两种操作:
1. 把区间 A 到 B 刷成 C 颜色。
2. 询问区间 A 到 B 有多少种不同的颜色。 (A 可能大于 B)
这题是赤裸裸的染色题,学会几点:
1. 用位运算来处理颜色。
2.延迟下放更新操作。(被延迟标记 坑了N 次WA。。。)
//Accepted 4796K 438MS G++ 2197B 2014-08-18 20:18:59 //Accepted 4272K 344MS C++ 2298B 2014-08-18 20:22:40 #include <iostream> #include <cstdio> using namespace std; /**线段树部分**/ #define MAX 200001 /**先前开了100万**/ struct Node { int left,right; int mark; int statu; }tree[3*MAX]; int creat(int root,int left,int right) { tree[root].left=left; tree[root].right=right; tree[root].mark=-1; /**延迟标记应该标记为 -1,WA了N次!就是写成0了!0代表1这种颜色,不能不下放!**/ if(left==right) return tree[root].statu=1; int mid=(right+left)>>1; return tree[root].statu=creat(2*root,left,mid)|creat(2*root+1,mid+1,right); } void up_mark(int root) { if(tree[root].mark>=0) { tree[root].statu=(1<<tree[root].mark); if(tree[root].left!=tree[root].right) tree[2*root].mark=tree[2*root+1].mark=tree[root].mark; tree[root].mark=-1; } } int up_data(int root,int left,int right,int vol) { up_mark(root); if(tree[root].left>right || tree[root].right<left) return tree[root].statu; if(tree[root].left>=left&&tree[root].right<=right) { tree[root].mark=vol; up_mark(root); return tree[root].statu; } return tree[root].statu=up_data(2*root,left,right,vol)|up_data(2*root+1,left,right,vol); } int calculate(int root,int left,int right) { up_mark(root); if(tree[root].left>right || tree[root].right<left) return 0; if(tree[root].left>=left&&tree[root].right<=right) return tree[root].statu; return calculate(2*root,left,right)|calculate(2*root+1,left,right); } /**线段树部分**/ int main() { int L,O,T; while(~scanf("%d%d%d",&L,&T,&O)) { creat(1,1,L); for(int i=1;i<=O;i++) { getchar(); char ch; int l,r,color; scanf("%c%d%d",&ch,&l,&r); if(l>r) swap(l,r); if(ch=='C') { scanf("%d",&color); up_data(1,l,r,color-1); } else { int st=calculate(1,l,r),ans=0; while(st) { if(st&1) ans++; st>>=1; } printf("%d\n",ans); } } } return 0; }
poj3277
这题需要用到这样的技巧:
二分建树时,这样二分 左子树(left,middle) 右子树(middle,right)
把线段树的叶子节点 设置为 ( l , l+1);
这样可以避免 左子树(left,middle) 右子树(middle+1,right)
导致的中间段没加上面积的情况!
//Accepted 7516K 485MS C++ 1752B 2014-09-26 21:51:23 #include <iostream> #include<cstdio> #include<algorithm> using namespace std; #define MAXN 41000 #define LL __int64 // 注意 楼真实下标,楼面积,楼高,都要用LL。线段树的下标可以用int struct node1 { LL a,b,h; bool operator<(const node1 &a )const { return h<a.h; } }built[MAXN]; LL s[MAXN*2]; int num; struct node { LL area,mark; int l,r; }tree[MAXN*6]; //因为一个楼,两个坐标,所以线段树范围是 MAXN*2*3 void built_tree(int rt,int l,int r) { tree[rt].l=l; tree[rt].r=r; tree[rt].area=0; tree[rt].mark=0; if(l==r-1) return; int m=(l+r)>>1; built_tree(rt<<1,l,m); built_tree(rt<<1|1,m,r); } void upmark(int rt) { if(tree[rt].mark) { int a=tree[rt].l; int b=tree[rt].r; tree[rt].area=tree[rt].mark*(s[b]-s[a]); if(tree[rt].l!=tree[rt].r-1) tree[rt<<1].mark=tree[rt<<1|1].mark=tree[rt].mark; tree[rt].mark=0; } } LL updata(int rt,int l,int r,int h) // 这里返回没用LL WA几发。。 { upmark(rt); if(tree[rt].l>=r || tree[rt].r<=l) return tree[rt].area; if(tree[rt].l>=l&&tree[rt].r<=r) { tree[rt].mark=h; upmark(rt); return tree[rt].area; } return tree[rt].area=updata(rt<<1,l,r,h)+updata(rt<<1|1,l,r,h);; } int main() { int N; scanf("%d",&N); num=0; for(int i=1;i<=N;i++) { scanf("%I64d%I64d%I64d",&built[i].a,&built[i].b,&built[i].h); s[num++]=built[i].a; s[num++]=built[i].b; } sort(s,s+num); int X=unique(s,s+num)-s; sort(built+1,built+1+N); built_tree(1,0,X); for(int i=1;i<=N;i++) { int a=lower_bound(s,s+X,built[i].a)-s; int b=lower_bound(s,s+X,built[i].b)-s; updata(1,a,b,built[i].h); } printf("%I64d\n",tree[1].area); return 0; }
POJ2828
题意:N 个人插队买票,给出两个值 id 和 val
表示 这个人插在第 id 个人的后面,他的价值为 val
问最后的输出顺序。。
分析:
这我真的一开始没想到是线段树,真的是题做少了。
如果正向的考虑,那么每插入一个进来,就会改变相对顺序,用链表肯定是超时的。
学会逆向思考,
从最后一个人开始,那么他的位置是肯定确定的,就是他前面必须有 id个人。
那么同理放好其它的人。
可以看下:
http://www.cnblogs.com/CheeseZH/archive/2012/04/29/2476134.html
的图示;
//Accepted 10736K 1594MS C++ 1543B #include <iostream> #include<cstdio> using namespace std; #define MAXN 300000 struct node { int id,val; }p[MAXN]; /**线段树部分**/ struct Node { int left,right,blank,val; }tree[3*MAXN]; int creat(int root,int left,int right) { tree[root].left=left; tree[root].right=right; if(left==right) return tree[root].blank=1; int a,b,mid; mid=(right-left)/2+left; a=creat(2*root,left,mid); b=creat(2*root+1,mid+1,right); return tree[root].blank=a+b; } int find(int root,int key,int v) { int l = 2*root; int r= 2*root+1; if(tree[root].left==tree[root].right) { tree[root].val = v; return tree[root].blank=0; } if(tree[l].blank < key) find(r,key-tree[l].blank,v); else find(l,key,v); return tree[root].blank=tree[l].blank+tree[r].blank; } int ans[MAXN],num; void show(int root) { if(tree[root].left==tree[root].right) { ans[num++] = tree[root].val; return ; } show(2*root); show(2*root+1); } /**线段树部分**/ int main() { int N; while(~scanf("%d",&N)) { for(int i=1;i<=N;i++) { scanf("%d%d",&p[i].id,&p[i].val); } creat(1,1,N); num=0; for(int i=N;i>=1;i--) { find(1,p[i].id+1,p[i].val); } show(1); printf("%d",ans[0]); for(int i=1;i<num;i++) { printf(" %d",ans[i]); } printf("\n"); } return 0; }
POJ2886
题意:
N个人顺时针站成一个圈,每个人手中有一张牌,牌上一个整数(不为0,可能为负数),从第k个开始出去,
他手中的整数,若是正整数就是顺时针的第几个继续出去,负数就是逆时针的第几个继续出去。
出去的第 i 个人 , p( i )指示 i 的约数个数。
问:约数个数最大的 那个人。
分析:
类似约瑟夫环,但是约瑟夫环,报第几个数出去是固定的。
首先,学到了个新知识--反素数:如果N 是N以内约数个数最多的数,则N就是一个反素数。
题目给出一个 N 即人的个数,那么只需要打出给出范围内的 所有反素数就可以找出 N以内约数个数最多的是 第几个。
现在第几个人是答案已经出来了,只需要知道这个人的名字就行,就是要知道他是谁。
如果用队列模拟这个过程,肯定超时,因为光是一次出队,都有可能执行 10^8。
上面已经做了个这样的题,就是线段树上找位置的。。
那么同理只需要每次找到位置就行了。。
注意一点:如果牌上是正整数 k ,那么顺时针找到的就是 p+k ,因为 p 这个人出队了, 所以p+k的相对顺序改变了,所有应该是编号 p+k-1 的人出去。
如果是负数,那么相对顺序不会改变。就是p+k。。 画个图就可以明白!
lower_bound(数组头,数组尾,k) 找出的是第一个小于 k 的数的上一个数下标,或者是等于k的数的下标。
没注意 RE了好多次。。
a存的是反素数,b存的是对应a中反素数 的约数个数。
//Accepted 24244K 1344MS C++ 1960B 2014-08-19 16:50:13 #include <iostream> #include<cstdio> #include<algorithm> using namespace std; #define MAXN 600000 const int a[37]={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160, 25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,500001}; const int b[37]={1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,80,84,90,96,100,108,120,128,144, 160,168,180,192,200,1314521}; int N,k; struct node { char name[20]; int id; }stu[MAXN]; /**线段树部分**/ struct Node { int left,right,blank; }tree[3*MAXN]; int creat(int root,int left,int right) { tree[root].left=left; tree[root].right=right; if(left==right) { return tree[root].blank=1; } int a,b,mid; mid=(right-left)/2+left; a=creat(2*root,left,mid); b=creat(2*root+1,mid+1,right); return tree[root].blank=a+b; } int find(int root,int key,int &ans) { int l = 2*root; int r= 2*root+1; if(tree[root].left==tree[root].right) { ans=tree[root].left; return tree[root].blank=0; } if(tree[l].blank < key) find(r,key-tree[l].blank,ans); else find(l,key,ans); return tree[root].blank=tree[l].blank+tree[r].blank; } /**线段树部分**/ int search(int n) { int tag=lower_bound(a,a+37,n)-a; if(n<a[tag]) tag--; /**如果不是等于的情况,这里就是第一个大于n的数,所以要--**/ return tag; } void solve() { creat(1,1,N); int goal=search(N); int ID=0; //从标号为ID 的人开始 stu[0].id=0; for(int i=0;i<a[goal];i++)/**模拟队**/ { int mod=tree[1].blank; if(stu[ID].id>0) k= ((k + stu[ID].id- 2)%mod+mod)%mod + 1;//因为从1开始所以就多减1 改变了相对顺序 总共就-2 else k= ((k + stu[ID].id-1)%mod+mod)%mod + 1; find(1,k,ID); } printf("%s %d\n",stu[ID].name,b[goal]); } int main() { while(~scanf("%d%d",&N,&k)) { for(int i=1;i<=N;i++) { scanf("%s%d",stu[i].name,&stu[i].id); } solve(); } return 0; }
省赛题---高桥低桥
首先建树肯定拿10^5 的下标建树!
只需 每次 在桥数组中找洪水的值 的上下界。相当于去淹下标!
最后就遍历一次各个节点,求出ans。
#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAX 110000 int val[MAX]; int n,m,k; struct Node { int left,right; int mark,total; }tree[MAX*3]; int creat(int root,int left,int right) { tree[root].left=left; tree[root].right=right; tree[root].mark=0; if(left==right) return tree[root].total=0; int mid=(right+left)/2; return tree[root].total=creat(2*root,left,mid)+creat(root*2+1,mid+1,right); } void up_mark(int root) { if(tree[root].mark) { tree[root].total+=tree[root].mark*(tree[root].right-tree[root].left+1); if(tree[root].left!=tree[root].right) { tree[2*root].mark+=tree[root].mark; tree[2*root+1].mark+=tree[root].mark; } tree[root].mark=0; } } int up_data(int root,int left,int right,int vol) { up_mark(root); if(tree[root].left>right || tree[root].right<left) return tree[root].total; if(tree[root].left>=left&&tree[root].right<=right) { tree[root].mark=vol; up_mark(root); return tree[root].total; } return tree[root].total=up_data(2*root,left,right,vol)+up_data(2*root+1,left,right,vol); } int calculate(int root,int left,int right) { up_mark(root); if(tree[root].left>right || tree[root].right<left) return 0; if(tree[root].left>=left&&tree[root].right<=right) return tree[root].total; return calculate(2*root,left,right)+calculate(2*root+1,left,right); } int main() { int cas=1; while(~scanf("%d%d%d",&n,&m,&k)) { for(int i=1;i<=n;i++) scanf("%d",&val[i]); sort(val+1,val+1+n); creat(1,1,n); int cur=1; for(int i=1;i<=m;i++) { int a,b; scanf("%d%d",&a,&b); int l=upper_bound(val+1,val+n+1,cur)-val; int r=upper_bound(val+1,val+n+1,a)-val; r--; cur=b; if(l<=r) up_data(1,l,r,1); } int ans=0; for(int i=1;i<=n;i++) { if(calculate(1,i,i)>=k) ans++;; } printf("Case %d: %d\n",cas++,ans); } return 0; }
区间合并
HDU1540
题意:D代表破坏村庄,R代表修复最后被破坏的那个村庄,Q代表询问包括x在内的最大连续区间是多少
分析:线段树节点 添加 三个域:当前区间最大连续长度 MAX ,左端点最大连续长度 , 右端点最大连续长度。
R 修复时,用栈来保存就行。
参考代码:
#include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> #include <stdlib.h> using namespace std; const int maxn = 50000+10; int n,m; int s[maxn],top;//s为模拟栈 struct node { int l,r; int ls,rs,ms;//ls,左端最大连续区间,rs右端最大连续区间,ms区间内最大连续区间 } a[maxn<<2]; void init(int l,int r,int i) { a[i].l = l; a[i].r = r; a[i].ls = a[i].rs = a[i].ms = r-l+1; if(l!=r) { int mid = (l+r)>>1; init(l,mid,i*2); init(mid+1,r,2*i+1); } } void insert(int i,int t,int x) { if(a[i].l == a[i].r) { if(x==1) a[i].ls = a[i].rs = a[i].ms = 1;//修复 else a[i].ls = a[i].rs = a[i].ms = 0;//破坏 return ; } int mid = (a[i].l+a[i].r)>>1; if(t<=mid) insert(2*i,t,x); else insert(2*i+1,t,x); a[i].ls = a[2*i].ls;//左区间 a[i].rs = a[2*i+1].rs;//右区间 a[i].ms = max(max(a[2*i].ms,a[2*i+1].ms),a[2*i].rs+a[2*i+1].ls);//父亲区间内的最大区间必定是,左子树最大区间,右子树最大区间,左右子树合并的中间区间,三者中最大的区间值 if(a[2*i].ls == a[2*i].r-a[2*i].l+1)//左子树区间满了的话,父亲左区间要加上右孩子的左区间 a[i].ls += a[2*i+1].ls; if(a[2*i+1].rs == a[2*i+1].r-a[2*i+1].l+1)//同理 a[i].rs += a[2*i].rs; } int query(int i,int t) { if(a[i].l == a[i].r || a[i].ms == 0 || a[i].ms == a[i].r-a[i].l+1)//到了叶子节点或者该访问区间为空或者已满都不必要往下走了 return a[i].ms; int mid = (a[i].l+a[i].r)>>1; if(t<=mid) { if(t>=a[2*i].r-a[2*i].rs+1)//因为t<=mid,看左子树,a[2*i].r-a[2*i].rs+1代表左子树右边连续区间的左边界值,如果t在左子树的右区间内,则要看右子树的左区间有多长并返回 return query(2*i,t)+query(2*i+1,mid+1); else return query(2*i,t);//如果不在左子树的右边界区间内,则只需要看左子树 } else { if(t<=a[2*i+1].l+a[2*i+1].ls-1)//同理 return query(2*i+1,t)+query(2*i,mid); else return query(2*i+1,t); } } int main() { int i,j,x; char ch[2]; while(~scanf("%d%d",&n,&m)) { top = 0; init(1,n,1); while(m--) { scanf("%s",ch); if(ch[0] == 'D') { scanf("%d",&x); s[top++] = x; insert(1,x,0); } else if(ch[0] == 'Q') { scanf("%d",&x); printf("%d\n",query(1,x)); } else { if(x>0) { x = s[--top]; insert(1,x,1); } } } } return 0; }
可持久化线段树
求第k小(第k大)。现在已经做的分为2类:(给定1~n的序列)
第一类:不断询问 1~m 中的第k小(第k大)。《优先队列,堆,线段树,Treap》
第二类:不断询问 某一区间 (m1,m2) 的第k小(第k大)。----比前一种更一般的情况。《主席树,Treap》
第三类:在第二类上还可以不断修改。----比前一种更一般的情况。
第一类不再赘述啦!
这里是第二类.
poj2104,poj2761,hdu2665.
#include <iostream> #include<cstdio> #include<algorithm> using namespace std; #define maxn 100010 int n,m; int ans[maxn]; struct Node { int a,b,id; }num[maxn]; bool cmp1(Node A,Node B) { return A.a<B.a; } bool cmp2(Node A,Node B) { return A.id<B.id; } struct T_node { T_node *left; T_node *right; int sum; }*root[maxn],nod[maxn*20]; int tot; void built(T_node*&p,int l,int r) { p=&nod[tot++]; p->sum=0; if(l==r) return ; int m=(l+r)>>1; built(p->left,l,m); built(p->right,m+1,r); } void updata(T_node*p,T_node*&q,int t,int l,int r) { q=&nod[tot++]; q->left=p->left; q->right=p->right; q->sum=p->sum+1; if(l==r)return ; int m=(l+r)>>1; if(t<=m) updata(p->left,q->left,t,l,m); else updata(p->right,q->right,t,m+1,r); } int query(T_node*p,T_node*q,int k,int l,int r) { if(l==r) return l; int m=(l+r)>>1; int cnt=q->left->sum - p->left->sum; if(k<=cnt) return query(p->left,q->left,k,l,m); else return query(p->right,q->right,k-cnt,m+1,r); } void gogogo() { int i; tot=0; int l,r,k; for( i=1;i<=n;i++) { scanf("%d",&num[i].a); num[i].id=i; } sort(num+1,num+1+n,cmp1); /**求出每个的相对大小,并去重另保存ans**/ int p; int sb=1; num[1].b=sb; ans[sb]=num[1].a; p=num[1].a; for( i=2;i<=n;i++) { if(p!=num[i].a) { p=num[i].a; sb++; } num[i].b=sb; ans[sb]=num[i].a; } /**按id排回来,建线段树! **/ sort(num+1,num+1+n,cmp2); /**先建一个root[0]树--相当于模板**/ built(root[0],1,sb); /**序列每个数都建一棵前缀线段树!**/ /**( 保存了前一棵的历史!)**/ for( i=1;i<=n;i++) updata(root[i-1],root[i],num[i].b,1,sb);/**这里果然傻逼了!把sb搞成p啦**/ /**两个前缀树相减==所求区间**/ /**(返回的是相对大小,就到ans里找序列原来的值)**/ while(m--) { scanf("%d%d%d",&l,&r,&k); int id=query(root[l-1],root[r],k,1,sb); printf("%d\n",ans[id]); } } int main() { // int T; //scanf("%d",&T); while(~scanf("%d%d",&n,&m)) { //; gogogo(); } return 0; }