这真是,又对着一棵线段树思考人生。== 蒟蒻如我比赛时如果碰到这种题是不是要直接弃疗了== 想的对也写不对><
线段树的每个节点记录两个量,该区间的区间和(有多少cells),该区间内某个叶子节点的最大值。
因为翻倍操作后,数字仍然是连续的,虽然输入的区间是线段树改变后的区间(线段树翻倍后节点会增多,树会变大),但是可以通过sum[rt]求出对应的原始区间。
1,2,3,4,5 翻倍后变为 1,2,3,4,5_1,5_2,如果查询的区间是[5,6],那么对于5,根据sum[rt]直接在左or右子区间递归求解即可,直到找到叶子节点为止。要注意右子树递归的index=index-sum[lc],因为右子区间的区间和是从rc开始计算的。
翻倍后每个叶子节点对应一个区间(num个同一种cell),但是query的区间可能只包括叶子节点的部分区间,例如
1, 2_1, 2_2, 3_1, 3_2, 3_3, 3_4, 4, 5_1, 5_2
1 2 3 4 5 6 7 8 9 9(对应的区间标号)
如果查询的区间是[3,6],那么只对应到原始线段树上leaf 2和leaf 3的部分区间,所以,需要对[2,5]进行区间操作,对3,6进行点操作。
For Update,在leaf 3加上sum[1~2]-3+1,因为输入的interval表示和,sum[rt]也表示区间和,这两者的关系就可以求出来。在leaf 6加上6-sum[1~(3-1)]。
For Query,需要返回sum[1~2]-3+1,6-sum[1~(3-1)],和区间查询的Max[rt]的最大值。
然后就是对着模板改啊改,模板里面求得是区间和,所以延迟标记是用add[rt]记录每个节点增加了多少值,所以PushDown的时候还要考虑到区间长度,而这里用add[rt]记录每个节点翻了多少倍,所以PushDown和区间长度无关,只要把sum[lc],sum[rc],Max[lc],Max[rc]*add[rt]即可。
PushDown是因为父节点的改变会影响子节点对应的区间值,所以只要有递归就要用到PushDown,即使木有对节点进行操作,个人感觉是因为之前可能有的延迟标记没有向下传递,不确定啊%>_<%
PushUp是因为子节点的改变会影响父节点,所以对于改变节点值的函数,在递归结束后都要用一下PushUp。
#include<iostream> #include<stdio.h> #include<cstdio> #include<stdlib.h> #include<vector> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<queue> #include <ctype.h> #include<map> #include<time.h> using namespace std; //hdu 4973 #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 #define LL long long const int maxn = 111111; int t; int n; int m; int cnt; /* Node Begin */ LL add[maxn<<2];//这一题里面是记录翻倍几次 LL sum[maxn<<2]; LL Max[maxn<<2]; /* Node End */ void PushUp(int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1]; Max[rt] = max(Max[rt<<1],Max[rt<<1|1]); } void PushDown(int rt) { //此处是翻了多少倍,和区间长度无关,所以不要参数m(之前是每个node+c,所以要考虑m) if (add[rt]) { add[rt<<1] += add[rt]; add[rt<<1|1] += add[rt]; sum[rt<<1] <<= add[rt]; sum[rt<<1|1] <<= add[rt]; Max[rt<<1] <<= add[rt]; Max[rt<<1|1] <<= add[rt]; add[rt] = 0; } } void build(int l,int r,int rt) { add[rt] = 0;//建树的时候没有翻倍记录 if (l == r) { sum[rt]=1; Max[rt]=1; return ; } int m = (l + r) >> 1; build(lson); build(rson); PushUp(rt); //cout<<"sum "<<sum[rt]<<endl; } int querylocation(int l,int r,int rt, LL index) { if(l==r) return l; PushDown(rt);//需要延迟处理,因为之前可能没有向下传递 int m = (l + r) >> 1; if(index<=sum[rt<<1]) { return querylocation(lson,index);//index比左边区间的和要小,所以在左边的区间内查询 } else { return querylocation(rson,index-sum[rt<<1]); //index如果比左边的区间和要大,那么在右边的区间查找,注意右边的区间和是不包括左边的,所以有index-sum[rt>>1] } PushUp(rt); } void updateinterval(int L,int R,int l,int r,int rt) {//L,R为查询区间 if (L <= l && r <= R) { add[rt]++; sum[rt]<<=1; Max[rt]<<=1; return ; } PushDown(rt);//父节点改变,会影响子节点 int m = (l + r) >> 1; if (L <= m) updateinterval(L , R , lson); if (m < R) updateinterval(L , R , rson); PushUp(rt);//子节点改变,会影响父节点 } void updateleaf(int L,int R,int c,int q, int rt) //q是要更新的节点 { if (L==R) { //add[rt] +=c; 点更新是不考虑翻倍(因为只能对应一个点中的一部分cell) sum[rt]+=c;//c=原先的区间和,此处相当于翻倍 Max[rt]+=c; return ; } PushDown(rt); int m = (L+R) >> 1; if (q <= m) updateleaf(L , m , c , q, rt<<1); if (m < q) updateleaf(m+1 , R , c , q , rt<<1|1); PushUp(rt); } LL querysum(int L,int R,int l,int r,int rt) { if (L <= l && r <= R) { return sum[rt]; } PushDown(rt); int m = (l+r) >> 1; LL ret = 0; if (L <= m) ret += querysum(L , R , lson); if (m < R) ret += querysum(L , R , rson); return ret; } void update(int L,int R,int l,int r,int rt) { if(l==r) { updateleaf(1,n,R-L+1,l,rt);//节点代表的区间会大于输入的区间 } else { int addl=querysum(1,l,1,n,1)-L+1;//最边缘的两个点要单独更新 int addr=R-querysum(1,r-1,1,n,1); updateleaf(1,n,addl,l,1); updateleaf(1,n,addr,r,1);//点更新 if(R-L>=2) { updateinterval(l+1,r-1,1,n,1);//中间的部分区间更新 } } } LL querymax(int L,int R,int l,int r,int rt) { if (L <= l && r <= R) { return Max[rt]; } PushDown(rt); int m = (l + r) >> 1; LL ret = 0; if (L <= m) ret =max(ret, querymax(L , R , lson)); if (m < R) ret =max(ret, querymax(L , R , rson)); return ret; } LL query(int L,int R,int l,int r,int rt) { LL ret=0; if(l==r)//本质上不是一种递归关系,所以不用考虑[l,r]区间包含的case { ret=R-L+1; } //PushDown(rt);没有递归,没有改变rt else { ret=max(ret,querysum(1,l,1,n,1)-L+1);//边沿的点考虑部分区间 ret=max(ret,R-querysum(1,r-1,1,n,1)); if(R-L>=2) { ret=max(ret,querymax(l+1,r-1,1,n,1)); } } return ret; } int main() { freopen("input.txt","r",stdin); scanf("%d",&t); int ca=1; while(t--) { scanf("%d %d",&n,&m); build(1,n,1); printf("Case #%d:\n",ca++); while(m--) { char op[2]; scanf("%s",&op); int x,y; if(op[0]=='Q') { scanf("%d %d",&x,&y);//cout<<op[0]<<" "<<x<<" "<<y<<endl; int l=querylocation(1,n,1,x); int r=querylocation(1,n,1,y); // cout<<m<<" "<<l<<" "<<r<<endl; printf("%I64d\n",query(x,y,l,r,1)); } else if(op[0]=='D') { scanf("%d %d",&x,&y);//cout<<op[0]<<" "<<x<<" "<<y<<endl; int l=querylocation(1,n,1,x); int r=querylocation(1,n,1,y); //cout<<m<<" "<<x<<" "<<y<<" "<<l<<" "<<r<<endl; update(x,y,l,r,1); } } } return 0; }