vijos1881 闪烁的繁星
描述
繁星, 漫天的繁星.
繁星排成一列, 我数一数呀, 一共有N只小星星呢.
星星们是听话的好孩子, 小岛在指挥它们跳舞呢.
舞蹈开始前, 它们都亮了起来!
小岛指一指第i只小星星, 只见第i只小星星立刻改变了自己的状态.
如果它之前是亮着的, 那么立刻就灭掉了.
如果它之前是灭掉的, 现在就立刻亮了呀!
如果说, 可以有连续若干只小星星.
其中任意相邻两只星星状态不同.
那就是最美的了.
小岛希望知道:
每一次发出指令之后
能找到最长的连续小星星, 满足上述需求的
有多长?
思路：赤裸裸的线段树，这是我做的第三个线段树，当然也是第一个updata比较长的。题意很好懂，但是updata比较的复杂，tree的结构体里要保存左右端点的颜色、最长长度和整个区间的最长长度，然后就是一个个的更新了。
#include<iostream> #include<cstdio> using namespace std; struct use{ int lc,rc,ls,rs,ws; }tree[10000001]; void updata(int i,int l,int r) { int mid; mid=(l+r)/2; tree[i].lc=tree[i*2].lc; tree[i].ls=tree[i*2].ls; tree[i].rc=tree[i*2+1].rc; tree[i].rs=tree[i*2+1].rs; tree[i].ws=max(tree[i*2].ws,tree[i*2+1].ws); if (tree[i*2].rc!=tree[i*2+1].lc) { tree[i].ws=max(tree[i].ws,tree[i*2].rs+tree[i*2+1].ls); if (tree[i*2].ws==mid-l+1) tree[i].ls=tree[i].ls+tree[i*2+1].ls; if (tree[i*2+1].ws==r-mid) tree[i].rs=tree[i].rs+tree[i*2].rs; } } void build(int i,int l,int r) { int mid; if (l==r) { tree[i].lc=tree[i].rc=0; tree[i].ws=tree[i].ls=tree[i].rs=1; return; } mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); updata(i,l,r); } void insert(int i,int l,int r,int k) { int mid; if (l==r&&l==k) { tree[i].lc=tree[i].rc=1-tree[i].lc; return; } mid=(l+r)/2; if (k<=mid) insert(i*2,l,mid,k); else insert(i*2+1,mid+1,r,k); updata(i,l,r); } int main() { int n,q,i,j,k; scanf("%d%d",&n,&q); build(1,1,n); for (i=1;i<=q;++i) { scanf("%d",&k); insert(1,1,n,k); printf("%d ",tree[1].ws); } }
POJ2828Buy Tickets
题意：给定n个人的有序入队位置，即第i+1行描述了第i个人插到第几个人后面，编号是多少。
思路： 又一次用到了倒着做的思想，先读入所有的数据，然后倒着插，因为这时候，描述每个人的第一个数字就是指这个人前面的空位数，而这个空位数就要用到线段树来维护了。tree表示的是这个区间内的空位数。每次插入的时候，就将这个点插到相对应的位置（若空格数小于左儿子的，就插入做儿子的区间；若大于左儿子，就将空格数减去左儿子的空格数再插入右儿子的区间），并更新tree。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int tree[800001]={0},ans[200001]={0},a[200001][2]={0}; void build(int i,int l,int r) { int mid; if (l==r) { tree[i]=1; return; } mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); tree[i]=tree[i*2]+tree[i*2+1]; } void insert(int i,int l,int r,int aa,int k) { int mid; if (l==r) { ans[l]=k; tree[i]=0; return; } mid=(l+r)/2; if (aa<=tree[i*2]) insert(i*2,l,mid,aa,k); else insert(i*2+1,mid+1,r,aa-tree[i*2],k); tree[i]=tree[i*2]+tree[i*2+1]; } int main() { int i,j,n; while(scanf("%d",&n)==1) { memset(ans,0,sizeof(ans)); memset(tree,0,sizeof(tree)); build(1,1,n); for (i=1;i<=n;++i) scanf("%d%d",&a[i][0],&a[i][1]); for (i=n;i>=1;--i) insert(1,1,n,a[i][0]+1,a[i][1]); for (i=1;i<n;++i) printf("%d ",ans[i]); printf("%d ",ans[n]); } }
Vijos1901学姐的钱包
描述
学姐每次出门逛街都要带恰好M元钱, 不过她今天却忘记带钱包了.
可怜的doc只好自己凑钱给学姐, 但是他口袋里只有一元钱.
好在doc的N位朋友们都特别有钱, 他们答应与doc作一些交换.
其中第i位朋友说:
如果doc有不少于Ri元钱,
doc可以把手上所有的钱都给这位朋友,
并从这位朋友手中换回Vi元钱,
但是这次交换会浪费Ti的时间.
doc希望可以在最短的时间内换到M元钱(其实是可以大于M的, 因为doc可以存私房钱呢), 否则学姐会生气的!
思路： 有点像有价值的线段覆盖，将线段右端点排序，离散之后对每一条线段的左右端点之间查询最小值，然后更新右端点处的最小值，最后，找到m到最右端的最小值就好了。用到了线段树。
#include<iostream> #include<cstdio> #include<queue> #include<algorithm> using namespace std; struct use{ int li,ri,ti; }a[500000]; int c[500000]={0}; long long tree[800001]={0},maxn=0x7ffffffffffffff; int my_comp(const use &x,const use &y) { if (x.ri<y.ri) return 1; return 0; } void build(int i,int l,int r) { int mid; if (l!=1) tree[i]=maxn; else tree[i]=0; if (l!=r) { mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); } } long long work(int i,int l,int r,int ll,int rr) { int mid; long long minn; if (ll<=l&&r<=rr) return tree[i]; mid=(l+r)/2; minn=maxn; if (ll<=mid) minn=min(minn,work(i*2,l,mid,ll,rr)); if (rr>mid) minn=min(minn,work(i*2+1,mid+1,r,ll,rr)); return minn; } void insert(int i,int l,int r,int ll,long long k) { int mid; if (l==r) { tree[i]=k; return; } mid=(l+r)/2; if (ll<=mid) insert(i*2,l,mid,ll,k); if (ll>mid) insert(i*2+1,mid+1,r,ll,k); tree[i]=min(tree[i*2],tree[i*2+1]); } int main() { int ci,t,i,j,n,m,size; long long ans,minn; scanf("%d",&t); for (ci=1;ci<=t;++ci) { scanf("%d%d",&n,&m); for (i=1;i<=n;++i) scanf("%d%d%d",&a[i].ri,&a[i].li,&a[i].ti); sort(a+1,a+n+1,my_comp); c[1]=1; for (i=1;i<=n;++i) c[i+1]=a[i].ri; size=unique(c+1,c+n+2)-c-1; build(1,1,size); for (i=1;i<=n;++i) if (a[i].ri>a[i].li) { a[i].ri=lower_bound(c+1,c+size+1,a[i].ri)-c; minn=work(1,1,size,lower_bound(c+1,c+size+1,a[i].li)-c,a[i].ri); if (minn!=maxn) insert(1,1,size,a[i].ri,minn+a[i].ti); else break; } printf("Case #%d: ",ci); ans=work(1,1,size,lower_bound(c+1,c+size+1,m)-c,size); if (ans!=maxn) printf("%lld ",ans); else printf("-1 "); } }
CODEVS1282 约瑟夫问题
题目描述 Description
有编号从1到N的N个小朋友在玩一种出圈的游戏。开始时N个小朋友围成一圈，编号为I+1的小朋友站在编号为I小朋友左边。编号为1的小朋友站在编号为N的小朋友左边。首先编号为1的小朋友开始报数，接着站在左边的小朋友顺序报数，直到数到某个数字M时就出圈。直到只剩下1个小朋友，则游戏完毕。现在给定N,M，求N个小朋友的出圈顺序。
思路：这些基本的类型有很多变换，如区间替换，空位查询等。本题就是用到了单点修改、区间查询。这里的单点查询并不知道具体位置，而知道在几个人之后，所以有一些复杂，不过对线段树熟练程度越高，也就越简单。
注意：这里的m要在每次有孩子出去的时候用另一个变量保存，并不断的与tree[1]（总人数）比较，因为有可能m比总人数大，这时候就要进行减了。同时必须是另开一个变量，不能再m上减（因为这个，wa了一次）。
#include<iostream> #include<cstdio> using namespace std; int tree[200000]={0},p; void build(int i,int l,int r) { int mid; if (l==r) { tree[i]=1; return; } mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); tree[i]=tree[i*2]+tree[i*2+1]; } int work(int i,int l,int r,int ll,int rr) { int mid,sum=0; if (ll<=l&&r<=rr) return tree[i]; mid=(l+r)/2; if (ll<=mid) sum+=work(i*2,l,mid,ll,rr); if (rr>mid) sum+=work(i*2+1,mid+1,r,ll,rr); return sum; } void insert(int i,int l,int r,int t) { int mid; if (l==r) { tree[i]=0; p=l; return; } mid=(l+r)/2; if (t<=tree[i*2]) insert(i*2,l,mid,t); else insert(i*2+1,mid+1,r,t-tree[i*2]); tree[i]=tree[i*2]+tree[i*2+1]; } int main() { int n,m,i,j,sum,t,mm; scanf("%d%d",&n,&m); build(1,1,n); p=0;t=n; while(t) { sum=work(1,1,n,p+1,n); mm=m; while (mm>tree[1]) mm-=tree[1]; if (mm>sum) insert(1,1,n,mm-sum); else insert(1,1,n,tree[1]-sum+mm); printf("%d ",p); --t; } printf(" "); }
CODEVS3304 水果姐逛水果街
题目描述 Description
水果姐今天心情不错，来到了水果街。
水果街有n家水果店，呈直线结构，编号为1~n，每家店能买水果也能卖水果，并且同一家店卖与买的价格一样。
学过oi的水果姐迅速发现了一个赚钱的方法：在某家水果店买一个水果，再到另外一家店卖出去，赚差价。
就在水果姐窃喜的时候，cgh突然出现，他为了为难水果姐，给出m个问题，每个问题要求水果姐从第x家店出发到第y家店，途中只能选一家店买一个水果，然后选一家店（可以是同一家店，但不能往回走）卖出去，求每个问题中最多可以赚多少钱。
思路：水果姐系列的线性问题，用线段树维护，节省时间。用结构体中的四项（区间最大、小值，区间最大贸易值（正、反））。这里有一个很巧妙的东西，就是对于区间[a，b]，它的最大、小值比较简单，但是最大贸易值由左右孩子区间的最大贸易值和左右区间的最大最小值的差值得到，进行更新。一开始用了四个数组，后来发现tle，于是就借鉴了dada的程序，改成了结构体，结果直接将tree的值更改了，只需返回值就可以了。
#include<iostream> #include<cstdio> using namespace std; struct use{ int maxi,mini,zan,fan; }tr[800000]; int a[200001]={0},n; void build(int i,int l,int r) { int mid; if (l==r) { tr[i].maxi=tr[i].mini=a[l]; return; } mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); tr[i].maxi=max(tr[i*2].maxi,tr[i*2+1].maxi); tr[i].mini=min(tr[i*2].mini,tr[i*2+1].mini); tr[i].zan=max(tr[i*2].zan,max(tr[i*2+1].zan,tr[i*2+1].maxi-tr[i*2].mini)); tr[i].fan=max(tr[i*2].fan,max(tr[i*2+1].fan,tr[i*2].maxi-tr[i*2+1].mini)); } struct use work(int i,int l,int r,int x,int y) { int mid,maxn=0; struct use tem,temm,temi; if (x>r||y<l) return (use){-1,2100000000,-1,-1}; if (x<=l&&r<=y) return tr[i]; mid=(l+r)/2; tem=work(i*2,l,mid,x,y); temm=work(i*2+1,mid+1,r,x,y); temi.maxi=max(tem.maxi,temm.maxi); temi.mini=min(tem.mini,temm.mini); temi.zan=max(tem.zan,max(temm.zan,temm.maxi-tem.mini)); temi.fan=max(tem.fan,max(temm.fan,tem.maxi-temm.mini)); return temi; } int main() { int m,i,j,x,y; struct use ans; scanf("%d",&n); for (i=1;i<=n;++i) scanf("%d",&a[i]); build(1,1,n); scanf("%d",&m); for (i=1;i<=m;++i) { scanf("%d%d",&x,&y); if (x==y) printf("0 "); else { if (x<y) { ans=work(1,1,n,x,y); printf("%d ",ans.zan); } else { ans=work(1,1,n,y,x); printf("%d ",ans.fan); } } } }
CODEVS1369 xth 砍树
题目大意：区间查询和，单点修改区间中点。
思路：比较简单的线段树，可是在double和float上栽了跟头，以后统一用double，输出printf里面用f，不要用llf（我zuo）。
#include<iostream> #include<cstdio> using namespace std; int tree[800000]={0},a[200001]={0}; void build(int i,int l,int r) { int mid; if (l==r) { tree[i]=a[l]; return; } mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); tree[i]=tree[i*2]+tree[i*2+1]; } int work(int i,int l,int r,int aa,int b) { int mid,sum=0; if (aa<=l&&r<=b) return tree[i]; mid=(l+r)/2; if (aa<=mid) sum+=work(i*2,l,mid,aa,b); if (b>mid) sum+=work(i*2+1,mid+1,r,aa,b); return sum; } void insert(int i,int l,int r,int aa) { int mid; if (l==r&&l==aa) { tree[i]=0; return; } mid=(l+r)/2; if (aa<=mid) insert(i*2,l,mid,aa); else insert(i*2+1,mid+1,r,aa); tree[i]=tree[i*2]+tree[i*2+1]; } int main() { int n,m,i,j,l,r,sum; double ans; scanf("%d",&n); for (i=1;i<=n;++i) scanf("%d",&a[i]); build(1,1,n); scanf("%d",&m); for (i=1;i<=m;++i) { scanf("%d%d",&l,&r); sum=work(1,1,n,l,r); insert(1,1,n,(l+r)/2); ans=sum*3.14; printf("%0.2f ",ans); } }
CODEVS1690 开关灯
题目大意：区间置反，区间查询。
思路：用delta数组表示区间置反的状态，这里就有出现了一个小问题，对于delta数组的思想不够了解，认识不够深入，其实delta数组表示的是这个节点的状态的累加，在每次pushdown的时候会将这个状态推至孩子，自己的状态清为0（大多数），所以在这个程序的paint中，delta[i]=!delta[i]，而不是delta[i]=0。以后应该好好理解最基本的东西，注意细节。
#include<iostream> #include<cstdio> using namespace std; int tree[400000]={0},delta[400000]={0}; void paint(int i,int l,int r) { tree[i]=r-l+1-tree[i]; delta[i]=!delta[i]; } void pushdown(int i,int l,int r) { int mid; mid=(l+r)/2; paint(i*2,l,mid); paint(i*2+1,mid+1,r); delta[i]=0; } void insert(int i,int l,int r,int a,int b) { int mid; if (a<=l&&r<=b) { paint(i,l,r); return; } if (delta[i]==1) pushdown(i,l,r); mid=(l+r)/2; if (a<=mid) insert(i*2,l,mid,a,b); if (b>mid) insert(i*2+1,mid+1,r,a,b); tree[i]=tree[i*2]+tree[i*2+1]; } int work(int i,int l,int r,int a,int b) { int mid,sum=0; if (a<=l&&r<=b) return tree[i]; if (delta[i]==1) pushdown(i,l,r); mid=(l+r)/2; if (a<=mid) sum+=work(i*2,l,mid,a,b); if (b>mid) sum+=work(i*2+1,mid+1,r,a,b); return sum; } int main() { int n,m,i,j,l,r,ans; scanf("%d%d",&n,&m); for (i=1;i<=m;++i) { scanf("%d%d%d",&j,&l,&r); if (j==0) insert(1,1,n,l,r); else { ans=work(1,1,n,l,r); printf("%d ",ans); } } }
CODEVS1228 苹果树
题目描述 Description
在卡卡的房子外面，有一棵苹果树。每年的春天，树上总会结出很多的苹果。卡卡非常喜欢吃苹果，所以他一直都精心的呵护这棵苹果树。我们知道树是有很多分叉点的，苹果会长在枝条的分叉点上面，且不会有两个苹果结在一起。卡卡很想知道一个分叉点所代表的子树上所结的苹果的数目，以便研究苹果树哪些枝条的结果能力比较强。
卡卡所知道的是，每隔一些时间，某些分叉点上会结出一些苹果，但是卡卡所不知道的是，总会有一些调皮的小孩来树上摘走一些苹果。
于是我们定义两种操作：
|
C x |
表示编号为x的分叉点的状态被改变(原来有苹果的话，就被摘掉，原来没有的话，就结出一个苹果) |
|
G x |
查询编号为x的分叉点所代表的子树中有多少个苹果 |
我们假定一开始的时候，树上全都是苹果，也包括作为根结点的分叉1。
思路：先用深搜建树（noip血淋淋的教训），给树的结点重新编号（因为是深搜的，所以一个节点孩子的编号是连续的），用新编的号做线段树，单点修改区间查询求和。
#include<iostream> #include<cstdio> using namespace std; struct use{ int ll,rr,bb; }tree1[100001]; int tree[400001]={0},bd[100001]={0},tot=0,next[200001]={0},point[100001]={0},en[200001]={0}; bool use[100001]={false}; void dfs(int i) { int y,t; use[i]=true; ++tot;t=tot; tree1[t].bb=i; bd[i]=t; y=point[i]; if (y!=0) tree1[t].ll=tot; while (y!=0) { if (!use[en[y]]) dfs(en[y]); y=next[y]; } tree1[t].rr=tot; } void build(int i,int l,int r) { int mid; if (l==r) { tree[i]=1; return; } mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); tree[i]=tree[i*2]+tree[i*2+1]; } void insert(int i,int l,int r,int a) { int mid; if (l==r&&l==a) { tree[i]=1-tree[i]; return; } mid=(l+r)/2; if (a<=mid) insert(i*2,l,mid,a); else insert(i*2+1,mid+1,r,a); tree[i]=tree[i*2]+tree[i*2+1]; } int work(int i,int l,int r,int a,int b) { int mid,sum=0; if (a<=l&&r<=b) return tree[i]; mid=(l+r)/2; if (a<=mid) sum+=work(i*2,l,mid,a,b); if (b>mid) sum+=work(i*2+1,mid+1,r,a,b); return sum; } int main() { int i,j,n,m,u,v,x,nn=0,ans; char ch; scanf("%d",&n); for (i=1;i<n;++i) { scanf("%d%d",&u,&v); ++nn; next[nn]=point[u]; point[u]=nn; en[nn]=v; ++nn; next[nn]=point[v]; point[v]=nn; en[nn]=u; } dfs(1); build(1,1,n); scanf("%d",&m); for (i=1;i<=m;++i) { scanf("%*c%*c%c%d",&ch,&x); if (ch=='C') insert(1,1,n,bd[x]); else { ans=work(1,1,n,tree1[bd[x]].ll,tree1[bd[x]].rr); printf("%d ",ans); } } }
一开始被坑了。。。rc！！！10*rc。。。原来是数据之间有换行。。。换行！！！
TYVJ1305最大子序和
题目大意：求长度不超过m的最大连续子序列的和。
思路：前缀和数组，然后以i为结尾的最大和等于sum[i]-min(sum[i-j])(0<=j<=m)。注意tree中保存的是sum数组的最小值，不要忘了把sum[0]加入进去，一开始wa了一个点。。。
#include<iostream> #include<cstdio> using namespace std; int tree[1200000]={0},a[300001]={0},sum[300001]={0}; void build(int i,int l,int r) { int mid; if (l==r) { tree[i]=sum[l]; return; } mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); tree[i]=min(tree[i*2],tree[i*2+1]); } int work(int i,int l,int r,int aa,int b) { int mid,summ; summ=2100000000; if (aa<=l&&r<=b) return tree[i]; mid=(l+r)/2; if (aa<=mid) summ=min(summ,work(i*2,l,mid,aa,b)); if (b>mid) summ=min(summ,work(i*2+1,mid+1,r,aa,b)); return summ; } int main() { int i,j,n,m,ans,summ; scanf("%d%d",&n,&m); for (i=1;i<=n;++i) { scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; } build(1,0,n); ans=0; for (i=1;i<=n;++i) { summ=work(1,0,n,max(0,i-m),i); if (sum[i]-summ>ans) ans=sum[i]-summ; } printf("%d",ans); }
CODEVS2492 上帝造题的七分钟2
题目描述 Description
XLk觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。
"第一分钟，X说，要有数列，于是便给定了一个正整数数列。
第二分钟，L说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。
第三分钟，k说，要能查询，于是便有了求一段数的和的操作。
第四分钟，彩虹喵说，要是noip难度，于是便有了数据范围。
第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。
第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。
第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。"
——《上帝造题的七分钟·第二部》
所以这个神圣的任务就交给你了。
思路：区间修改，区间查询。。。开方！！！求和！！！逗我。。。单点修改，区间查询，tle。。。玩我。。。后来lcomyn看了大神的博客结合自己的思想a了。。。于是开始优化，思路同化。对于一个区间中代表的各点都是0或1就不需要更改了，一个数组标记一下来记住是否需要更改。这个题中没有lazy，直接更改到底。
#include<iostream> #include<cstdio> #include<cmath> using namespace std; long long tree[400000]={0},a[100001]={0}; bool tree1[400000]={false}; void build(int i,int l,int r) { int mid; if (l==r) { tree[i]=a[l]; if (a[l]<=1) tree1[i]=true; return; } mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); tree[i]=tree[i*2]+tree[i*2+1]; } void updata(int i,int l,int r) { int mid; if (tree1[i]) return; if (l==r) { tree[i]=floor(sqrt(tree[i])); if (tree[i]<=1) tree1[i]=true; return; } mid=(l+r)/2; updata(i*2,l,mid); updata(i*2+1,mid+1,r); tree[i]=tree[i*2]+tree[i*2+1]; if (tree1[i*2]&&tree1[i*2+1]) tree1[i]=true; } void insert(int i,int l,int r,int aa,int b) { int mid; if (aa<=l&&r<=b) { updata(i,l,r); return; } mid=(l+r)/2; if (aa<=mid) insert(i*2,l,mid,aa,b); if (b>mid) insert(i*2+1,mid+1,r,aa,b); tree[i]=tree[i*2]+tree[i*2+1]; if (tree1[i*2]&&tree1[i*2+1]) tree1[i]=true; } long long work(int i,int l,int r,int aa,int b) { int mid; long long sum=0; if (aa<=l&&r<=b) return tree[i]; mid=(l+r)/2; if (aa<=mid) sum+=work(i*2,l,mid,aa,b); if (b>mid) sum+=work(i*2+1,mid+1,r,aa,b); return sum; } int main() { int n,m,i,j,x,y,t; long long ans; scanf("%d",&n); for (i=1;i<=n;++i) scanf("%lld",&a[i]); build(1,1,n); scanf("%d",&m); for (i=1;i<=m;++i) { scanf("%d%d%d",&t,&x,&y); if (x>y) { j=x;x=y;y=j; } if (t==0) insert(1,1,n,x,y); else { ans=work(1,1,n,x,y); printf("%lld ",ans); } } }
codevs3243区间翻转
题目描述 Description
给出N个数，要求做M次区间翻转（如1 2 3 4变成4 3 2 1），求出最后的序列。
思路：因为这里的数据范围有特殊意义，交换的区间一定是线段树上的一个结点，所以就很简单了。但是，和我平时写的线段树不同，需要保存叶节点的位置，和每个节点的左右孩子节点的编号，用delta数组。
#include<iostream> #include<cstdio> using namespace std; int a[150001]={0},tree[600000]={0},ls[600000]={0},rs[600000]={0}; bool delta[600000]={false}; void build(int i,int l,int r) { int mid; if (l==r) { tree[i]=l; return; } mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); ls[i]=i*2;rs[i]=i*2+1; } void paint(int i) { int t; delta[i]=!delta[i]; t=ls[i];ls[i]=rs[i];rs[i]=t; } void pushdown(int i) { paint(ls[i]); paint(rs[i]); delta[i]=false; } void insert(int i,int l,int r,int aa,int b) { int mid; if (l==aa&&r==b) { paint(i); return; } mid=(l+r)/2; if (delta[i]) pushdown(i); if (b<=mid) insert(ls[i],l,mid,aa,b); else insert(rs[i],mid+1,r,aa,b); } void print(int i) { if (tree[i]!=0) { printf("%d ",a[tree[i]]); return; } if (delta[i]) pushdown(i); print(ls[i]); print(rs[i]); } int main() { int n,m,i,j,aa,b; scanf("%d",&n); for (i=1;i<=n;++i) scanf("%d",&a[i]); build(1,1,n); scanf("%d",&m); for (i=1;i<=m;++i) { scanf("%d%d",&aa,&b); insert(1,1,n,aa,b); } print(1); }
cogs1272行星序列
题目大意：
“神州“载人飞船的发射成功让小可可非常激动，他立志长大后要成为一名宇航员假期一始，他就报名参加了“小小宇航员夏令营”，在这里小可可不仅学到了丰富的宇航知识，还参与解决了一些模拟飞行中发现的问题，今天指导老师交给他一个任务，在这次模拟飞行的路线上有N个行星，暂且称它们为一个行星序列，并将他们从1至n标号，在宇宙未知力量的作用下这N个行星的质量是不断变化的，所以他们对飞船产生的引力也会不断变化，小可可的任务就是在飞行途中计算这个行星序列中某段行星的质量和，以便能及时修正飞船的飞行线路，最终到达目的地，行星序列质量变化有两种形式：
1，行星序列中某一段行星的质量全部乘以一个值
2，行星序列中某一段行星的质量全部加上一个值
由于行星的质量和很大，所以求出某段行星的质量和后只要输出这个值模P的结果即可，小可可被这个任务难住了，聪明的你能够帮他完成这个任务吗？
思路：这个题目有些不同，一开始以为只要做两套pushdown就可以了，可是后来发现操作的顺序对于结果有影响，先乘后加和先加后乘是不同的。所以我们在这里定义一个新运算：*m+c。delta存两个量，加的和乘的，更新delta，对于乘的就是直接乘，加就是先乘后加。（具体的见代码）注意中间的longlong。
这次又出现一个神错：读入的longlong变量c一开始没清零，结果结果出现了负数。。。
#include<cstdio> #include<iostream> #include<cstring> using namespace std; long long tree[400000]={0},delta[400000][2]={0},a[100001]={0},p; void build(int i,int l,int r) { int mid; if (l==r) { tree[i]=a[l]%p; return; } mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); tree[i]=(tree[i*2]+tree[i*2+1])%p; } void paint(int i,int l,int r,long long m,long long c) { tree[i]=((tree[i]*m)%p+(r-l+1)*c)%p; delta[i][0]=(delta[i][0]*m)%p; delta[i][1]=((delta[i][1]*m)%p+c)%p; } void pushdown(int i,int l,int r) { int mid; mid=(l+r)/2; paint(i*2,l,mid,delta[i][0],delta[i][1]); paint(i*2+1,mid+1,r,delta[i][0],delta[i][1]); delta[i][0]=1;delta[i][1]=0; } void insert(int i,int l,int r,int aa,int b,long long m,long long c) { int mid; if (aa<=l&&r<=b) { paint(i,l,r,m,c); return; } pushdown(i,l,r); mid=(l+r)/2; if (aa<=mid) insert(i*2,l,mid,aa,b,m,c); if (b>mid) insert(i*2+1,mid+1,r,aa,b,m,c); tree[i]=(tree[i*2]+tree[i*2+1])%p; } long long work(int i,int l,int r,int aa,int b) { int mid; long long sum=0; if (aa<=l&&r<=b) { tree[i]=tree[i]%p; return tree[i]; } pushdown(i,l,r); mid=(l+r)/2; if (aa<=mid) sum=(sum+work(i*2,l,mid,aa,b))%p; if (b>mid) sum=(sum+work(i*2+1,mid+1,r,aa,b))%p; return sum; } int main() { freopen("seqb.in","r",stdin); freopen("seqb.out","w",stdout); int n,i,j,t,g,m,kind; long long ans,c=0; scanf("%d%lld",&n,&p); for (i=1;i<=n;++i) scanf("%lld",&a[i]); build(1,1,n); for (i=1;i<=399999;++i) delta[i][0]=1; scanf("%d",&m); for (i=1;i<=m;++i) { scanf("%d%d%d",&kind,&t,&g); if (kind==1) { scanf("%lld",&c); insert(1,1,n,t,g,c,0); } if (kind==2) { scanf("%lld",&c); insert(1,1,n,t,g,1,c); } if (kind==3) { ans=work(1,1,n,t,g)%p; printf("%lld ",ans); } } fclose(stdin); fclose(stdout); }
cogs1008 贪婪大陆
题目大意：在一个给定区间内进行两种操作：给区间内每一个位置加上一个相同的与之前所放物品都不同的物品；查询区间内有几种物品。对于每一个查询都输出相应的结果。
思路:看到这个题目的时候有了一种错误的思路，以为是个简单的区间求和，可是仔细研究后发现并不是这样的。并不是将区间内的最大值或者和输出，因为有的时候可能两个相邻的区间放入物品，会默认为一个了，这样就出现了错误。于是就开始寻找思路(感谢dada)。我们可以将每个区间的左右端点插入到不同的树中，一个区间内物品的个数，其实就是1~r中左端点的个数减去1~(l-1）中右端点的个数，然后输出就可以了。这种类似于前缀和的思路要熟练掌握。
#include<iostream> #include<cstdio> using namespace std; int tree[400000][2]={0}; void insert1(int i,int l,int r,int a) { int mid; if (l==r&&l==a) { tree[i][0]++; return; } mid=(l+r)/2; if (a<=mid) insert1(i*2,l,mid,a); else insert1(i*2+1,mid+1,r,a); tree[i][0]=tree[i*2][0]+tree[i*2+1][0]; } void insert2(int i,int l,int r,int a) { int mid; if (l==r&&l==a) { tree[i][1]++; return; } mid=(l+r)/2; if (a<=mid) insert2(i*2,l,mid,a); else insert2(i*2+1,mid+1,r,a); tree[i][1]=tree[i*2][1]+tree[i*2+1][1]; } int work1(int i,int l,int r,int a,int b) { int mid,sum=0; if (a<=l&&r<=b) return tree[i][0]; mid=(l+r)/2; if (a<=mid) sum+=work1(i*2,l,mid,a,b); if (b>mid) sum+=work1(i*2+1,mid+1,r,a,b); return sum; } int work2(int i,int l,int r,int a,int b) { int mid,sum=0; if (a<=l&&r<=b) return tree[i][1]; mid=(l+r)/2; if (a<=mid) sum+=work2(i*2,l,mid,a,b); if (b>mid) sum+=work2(i*2+1,mid+1,r,a,b); return sum; } int main() { freopen("greedisland.in","r",stdin); freopen("greedisland.out","w",stdout); int n,m,i,j,q,l,r,ans1,ans2; scanf("%d%d",&n,&m); for (i=1;i<=m;++i) { scanf("%d%d%d",&q,&l,&r); if (q==1) { insert1(1,1,n,l); insert2(1,1,n,r); } else { ans1=work1(1,1,n,1,r); if (l==1) ans2=0; else ans2=work2(1,1,n,1,l-1); printf("%d ",ans1-ans2); } } fclose(stdin); fclose(stdout); }
cogs265线段覆盖
题目大意：给区间放上或拿走黑布条，统计总区间内黑区间的个数和长度。
思路：线段树的区间覆盖，因为这个题没有查询操作，所以可以不用pushdown。然后就是updata和insert操作了。updata中要判断delta的值，然后进行更新（是清成全黑，或者根据孩子更新）；insert中对于找到的区间要看是否为单元素的，若为单元素的则直接更新，否则要判断delta的范围来进行。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; struct use{ int lc,rc,sum,len; }tree[800000]; int delta[800000]={0}; void updata(int i,int l,int r) { int mid; if (delta[i]>0) { tree[i].lc=tree[i].rc=tree[i].sum=1;tree[i].len=r-l+1; } else { tree[i].lc=tree[i*2].lc;tree[i].rc=tree[i*2+1].rc; tree[i].sum=tree[i*2].sum+tree[i*2+1].sum; if (tree[i*2].rc==tree[i*2+1].lc&&tree[i*2].rc==1) --tree[i].sum; tree[i].len=tree[i*2].len+tree[i*2+1].len; } } void insert(int i,int l,int r,int a,int b,int x) { int mid,tt; if (a<=l&&r<=b) { delta[i]+=x; if (l!=r) updata(i,l,r); else { if (delta[i]) tt=1; else tt=0; tree[i].lc=tree[i].rc=tt; tree[i].sum=tt;tree[i].len=tt; } return; } mid=(l+r)/2; if (a<=mid) insert(i*2,l,mid,a,b,x); if (b>mid) insert(i*2+1,mid+1,r,a,b,x); updata(i,l,r); } int main() { freopen("xdfg.in","r",stdin); freopen("xdfg.out","w",stdout); int i,j,l,n,a,t,m; scanf("%d%d",&l,&n); for (i=1;i<=n;++i) { scanf("%d%d%d",&m,&a,&t); if (m==1) insert(1,0,l,a,a+t-1,1); else insert(1,0,l,a,a+t-1,-1); printf("%d %d ",tree[1].sum,tree[1].len); } fclose(stdin); fclose(stdout); }
cogs775山海经
题目大意：在给定区间内找到最大的连续子段和。
思路：机房中的大神a了之后，在机房说思路，结果就弱弱的听到了，然后就。。。写了好久啊。。。这是一个线段树中保存很多状态的题，我们要更新这个区间的最大最小值，他们的位置，最大差和起止点。然后就是很简单但长达三十行的updata，然后就是弱弱的查询了。每个区间的最大差都是左右区间最大差和右区间最大值-左区间最小值中的较大值，然后保存下来，注意更新的顺序，能不用处理相等的情况就满足起止点最小的条件。
（一开始updata里面没有返回值，查了半个小时。。。要疯了！！！）
#include<iostream> #include<cstdio> using namespace std; struct use{ int maxi,mini,maxcha,st,en,pmax,pmin; }tree[400001]; int sum[100001]={0}; struct use updata(struct use ans1,struct use ans2) { struct use ans; if (ans1.maxi>=ans2.maxi) { ans.maxi=ans1.maxi;ans.pmax=ans1.pmax; } else { ans.maxi=ans2.maxi;ans.pmax=ans2.pmax; } if (ans1.mini<=ans2.mini) { ans.mini=ans1.mini;ans.pmin=ans1.pmin; } else { ans.mini=ans2.mini;ans.pmin=ans2.pmin; } ans.maxcha=-2100000000; if (ans1.maxcha>ans.maxcha) { ans.maxcha=ans1.maxcha;ans.st=ans1.st;ans.en=ans1.en; } if (ans2.maxi-ans1.mini>ans.maxcha) { ans.maxcha=ans2.maxi-ans1.mini;ans.st=ans1.pmin;ans.en=ans2.pmax; } if (ans2.maxcha>ans.maxcha) { ans.maxcha=ans2.maxcha;ans.st=ans2.st;ans.en=ans2.en; } return ans; } void build(int i,int l,int r) { int mid; if (l==r) { tree[i].maxi=tree[i].mini=sum[l]; tree[i].maxcha=-2100000000;tree[i].st=tree[i].en=tree[i].pmax=tree[i].pmin=l; return; } mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); tree[i]=updata(tree[i*2],tree[i*2+1]); } struct use work(int i,int l,int r,int a,int b) { struct use ans1,ans2,ans; int mid; ans1.maxi=ans2.maxi=-1000000000;ans1.maxcha=ans2.maxcha=-2100000000;ans1.mini=ans2.mini=1000000000; if (a<=l&&r<=b) return tree[i]; mid=(l+r)/2; if (a<=mid) ans1=work(i*2,l,mid,a,b); if (b>mid) ans2=work(i*2+1,mid+1,r,a,b); ans=updata(ans1,ans2); return ans; } int main() { freopen("hill.in","r",stdin); freopen("hill.out","w",stdout); int n,m,a,b,i,j; struct use ans; scanf("%d%d",&n,&m); for (i=1;i<=n;++i) { scanf("%d",&j); sum[i]=sum[i-1]+j; } build(1,0,n); for (i=1;i<=m;++i) { scanf("%d%d",&a,&b); ans=work(1,0,n,a-1,b); printf("%d %d %d ",ans.st+1,ans.en,ans.maxcha); } fclose(stdin); fclose(stdout); }
cogs1365软件安装
题目大意：找到最早的一个长度大于等于要求的给定区间，放一个软件。或者将一个区间释放。
思路：用结构体保存左右结点颜色和长度，区间最长长度。然后每次放一个软件的时候要将这个区间覆盖成1，释放的时候覆盖成0。一开始pushdown的时候没有判断delta是否为0（这里是覆盖，所以一定要判断，不然就。。。），最后把数组开大了一倍，然后才a。。。
#include<iostream> #include<cstdio> using namespace std; struct use{ int lc,rc,ls,rs,ms; }tree[400000]; int delta[400000]={0}; void updata(int i,int l,int r) { int mid; mid=(l+r)/2; tree[i].lc=tree[i*2].lc;tree[i].rc=tree[i*2+1].rc; tree[i].ls=tree[i*2].ls;tree[i].rs=tree[i*2+1].rs; tree[i].ms=max(tree[i*2].ms,tree[i*2+1].ms); if (tree[i*2].rc==tree[i*2+1].lc&&tree[i*2].rc==0) { tree[i].ms=max(tree[i].ms,tree[i*2].rs+tree[i*2+1].ls); if (tree[i].ls==mid-l+1) tree[i].ls=tree[i].ls+tree[i*2+1].ls; if (tree[i].rs==r-mid) tree[i].rs=tree[i].rs+tree[i*2].rs; } } void build(int i,int l,int r) { int mid; if (l==r) { tree[i].lc=tree[i].rc=0; tree[i].ls=tree[i].rs=tree[i].ms=1; return; } mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); updata(i,l,r); } void paint(int i,int l,int r,int x) { if (x==1) { tree[i].ls=tree[i].rs=tree[i].ms=r-l+1; tree[i].lc=tree[i].rc=0; } if (x==2) { tree[i].ls=tree[i].rs=tree[i].ms=0; tree[i].lc=tree[i].rc=1; } delta[i]=x; } void pushdown(int i,int l,int r) { int mid; mid=(l+r)/2; paint(i*2,l,mid,delta[i]); paint(i*2+1,mid+1,r,delta[i]); delta[i]=0; } int work(int i,int l,int r,int st) { int mid; mid=(l+r)/2; if (delta[i]!=0) pushdown(i,l,r); if (tree[i].ls>=st) return l; if (tree[i*2].ms>=st) return work(i*2,l,mid,st); if (tree[i*2].rs+tree[i*2+1].ls>=st) return (mid-tree[i*2].rs+1); if (tree[i*2+1].ms>=st) return work(i*2+1,mid+1,r,st); if (tree[i].rs>=st) return (r-tree[i].rs+1); } void insert(int i,int l,int r,int a,int b,int x) { int mid; if (delta[i]!=0) pushdown(i,l,r); if (a<=l&&r<=b) { paint(i,l,r,x); return; } mid=(l+r)/2; if (a<=mid) insert(i*2,l,mid,a,b,x); if (b>mid) insert(i*2+1,mid+1,r,a,b,x); updata(i,l,r); } int main() { freopen("haoi13t4.in","r",stdin); freopen("haoi13t4.out","w",stdout); int n,m,i,j,kind,di,mi,po; scanf("%d%d",&n,&m); build(1,1,n); for (i=1;i<=m;++i) { scanf("%d",&kind); if (kind==1) { scanf("%d",&mi); if (tree[1].ms<mi) printf("0 "); else { po=work(1,1,n,mi); printf("%d ",po); insert(1,1,n,po,po+mi-1,2); } } else { scanf("%d%d",&di,&mi); insert(1,1,n,di,di+mi-1,1); } } fclose(stdin); fclose(stdout); }
cogs421HH的项链
题目大意：统计区间内元素的种类数。
思路：用了差分序列的思想，对于一种颜色，把这种颜色上一个位置之后的+1，当前位置的下一位-1，这样就能保证线段树中的这个区间是+1，最后查询1~每个查询的左端点的和（差分序列的和），就是答案了。
这个左端点困惑了我很久，现在终于明白了，因为只需要加到在这个区间里就可以了，（这里从左到右，保证了右端点一定在，只要在左端点右边就可以了），所以只需要加到左端点处。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct use{ int ll,rr,po; }ask[200001]; int ans[200001]={0},co[50001]={0},la[1000001]={0},tree[200001]={0}; int my_comp(const use &a,const use &b) { if (a.rr<b.rr) return 1; return 0; } void insert(int i,int l,int r,int a,int x) { int mid; if (l==r) { tree[i]+=x; return; } mid=(l+r)/2; if (a<=mid) insert(i*2,l,mid,a,x); else insert(i*2+1,mid+1,r,a,x); tree[i]=tree[i*2]+tree[i*2+1]; } int work(int i,int l,int r,int a,int b) { int mid,sum=0; if (a<=l&&r<=b) return tree[i]; mid=(l+r)/2; if (a<=mid) sum+=work(i*2,l,mid,a,b); if (b>mid) sum+=work(i*2+1,mid+1,r,a,b); return sum; } int main() { freopen("diff.in","r",stdin); freopen("diff.out","w",stdout); int n,m,i,j,l,r; scanf("%d",&n); for (i=1;i<=n;++i) scanf("%d",&co[i]); scanf("%d",&m); for (i=1;i<=m;++i) { scanf("%d%d",&ask[i].ll,&ask[i].rr); ask[i].po=i; } sort(ask+1,ask+m+1,my_comp); j=1; for (i=1;i<=n;++i) { insert(1,1,n+1,la[co[i]]+1,1); insert(1,1,n+1,i+1,-1); la[co[i]]=i; while (i==ask[j].rr) { ans[ask[j].po]=work(1,1,n+1,1,ask[j].ll); ++j; } if (j>m) break; } for (j=1;j<=m;++j) printf("%d ",ans[j]); fclose(stdin); fclose(stdout); }
poj1151Atlantis
题目大意：矩形面积合并。
思路：扫描线。先离散（这里可以不用把具体的数保存在数组里，可以边做边求整数），将矩形的上下边加入到一个结构体里保存，左右端点、高度（纵坐标）、种类（是上边还是下边），然后就是将这些边排个升序，从下往上把边加入到线段树中（下边就+，上边就-），这里有一个小小的优化：因为我们不需要将标记下放，所以可以对一个区间的值直接求解，而不用pushdown。线段树中统计了这个区间中被边覆盖的长度（在更新长度的时候就用到了之前离散化的数组中的原值），这里的线段树中的结点并不是坐标点，而是两个坐标点之间的线段，所以要从1到n-1，每做一次就把ans+tree[1]*(bian[i+1].h-bian[i].h)。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; struct use{ double ll,rr,h; int kind,li,ri; }xian[10000]; double tree[400000]={0},cc[10000]={0}; int delta[400000]={0}; int my_comp(const use &a,const use &b) { if (a.h<b.h) return 1; return 0; } void updata(int i,int l,int r) { if (delta[i]>0) tree[i]=cc[r+1]-cc[l]; else { if (l==r) tree[i]=0; else tree[i]=tree[i*2]+tree[i*2+1]; } } void insert(int i,int l,int r,int a,int b,int x) { int mid; if (a<=l&&r<=b) { delta[i]+=x; updata(i,l,r); return; } mid=(l+r)/2; if (a<=mid) insert(i*2,l,mid,a,b,x); if (b>mid) insert(i*2+1,mid+1,r,a,b,x); updata(i,l,r); } int main() { int n,i,j,tot=0,tot2=0,l,r,ci=0,size; double a,b,c,d,ans; while(scanf("%d",&n)==1) { if (n==0) break; ++ci;tot=0;tot2=0;ans=0; memset(xian,0,sizeof(xian)); memset(tree,0,sizeof(tree)); memset(delta,0,sizeof(delta)); for (i=1;i<=n;++i) { scanf("%lf%lf%lf%lf",&a,&b,&c,&d); ++tot;xian[tot].ll=a;xian[tot].rr=c;xian[tot].h=b;xian[tot].kind=1; ++tot;xian[tot].ll=a;xian[tot].rr=c;xian[tot].h=d;xian[tot].kind=-1; ++tot2;cc[tot2]=a; ++tot2;cc[tot2]=c; } sort(cc+1,cc+tot2+1); size=unique(cc+1,cc+tot2+1)-cc-1; sort(xian+1,xian+tot+1,my_comp); for (i=1;i<tot;++i) { xian[i].li=upper_bound(cc+1,cc+size+1,xian[i].ll)-cc-1; xian[i].ri=upper_bound(cc+1,cc+size+1,xian[i].rr)-cc-1; if (xian[i].li<xian[i].ri) insert(1,1,size-1,xian[i].li,xian[i].ri-1,xian[i].kind); ans=ans+tree[1]*(xian[i+1].h-xian[i].h); } printf("Test case #%d Total explored area: %0.2f ",ci,ans); } }
cogs263矩形周长
题目大意：矩形周长合并。
思路：扫描线。这道题的范围比较小，可以不离散（
主要是因为我一开始离散，然后错了），同面积，只是要保存端点的有无边和竖边的个数。然后稍微改一下updata。最后ans+=abs(tree[1].len-last);
ans+=tree[1].dd*(xian[i+1].h-xian[i].h);注意重边的合并。这里有负下标，所以向右移了10000（莫名的re。。。）
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; struct use{ int ll,rr,h,kind; }xian[100000]; struct uses{ int len,dd; bool lb,rb; }tree[100000]; int delta[100000]={0}; int my_comp(const use &a,const use &b) { if (a.h<b.h) return 1; return 0; } void updata(int i,int l,int r) { if (delta[i]>0) { tree[i].len=r-l+1; tree[i].dd=2; tree[i].lb=tree[i].rb=true; } else { if (l==r) { tree[i].len=tree[i].dd=0;tree[i].lb=tree[i].rb=false; } else { tree[i].len=tree[i*2].len+tree[i*2+1].len; tree[i].lb=tree[i*2].lb;tree[i].rb=tree[i*2+1].rb; tree[i].dd=tree[i*2].dd+tree[i*2+1].dd; if (tree[i*2].rb&&tree[i*2+1].lb) tree[i].dd-=2; } } } void insert(int i,int l,int r,int a,int b,int x) { int mid; if (a<=l&&r<=b) { delta[i]+=x; updata(i,l,r); return; } mid=(l+r)/2; if (a<=mid) insert(i*2,l,mid,a,b,x); if (b>mid) insert(i*2+1,mid+1,r,a,b,x); updata(i,l,r); } int main() { freopen("picture.in","r",stdin); freopen("picture.out","w",stdout); int n,i,j,l,r,a,b,c,d,tot=0,size,ans=0,last=0,ml,mr; scanf("%d",&n); ml=20000;mr=0; for (i=1;i<=n;++i) { scanf("%d%d%d%d",&a,&b,&c,&d); a+=10000;b+=10000;c+=10000;d+=10000; ++tot;xian[tot].ll=a;xian[tot].rr=c;xian[tot].h=b;xian[tot].kind=1; ++tot;xian[tot].ll=a;xian[tot].rr=c;xian[tot].h=d;xian[tot].kind=-1; ml=min(ml,a); mr=max(mr,c); } sort(xian+1,xian+tot+1,my_comp); for (i=1;i<=tot;++i) { if (xian[i].ll<xian[i].rr) insert(1,ml,mr-1,xian[i].ll,xian[i].rr-1,xian[i].kind); ans+=abs(tree[1].len-last); ans+=tree[1].dd*(xian[i+1].h-xian[i].h); last=tree[1].len; } printf("%d ",ans); fclose(stdin); fclose(stdout); }
当然这个题也可以不用线段树做，dada大神用了神奇的差分序列，附上code。神神神神！！！
#include<iostream> using namespace std; #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> int delta[10002]; int main(){ int left[5000],right[5000],down[5000],up[5000],X[10000],Y[10000],N,i,j; freopen("picture.in","r",stdin); freopen("picture.out","w",stdout); scanf("%d",&N); for(i=0;i<N;++i){ scanf("%d%d%d%d",left+i,down+i,right+i,up+i); X[i]=left[i]; X[i+N]=right[i]; Y[i]=down[i]; Y[i+N]=up[i]; } sort(X,X+(N<<1)),sort(Y,Y+(N<<1)); int xtot=unique(X,X+(N<<1))-X,ytot=unique(Y,Y+(N<<1))-Y; for(i=0;i<N;++i){ left[i]=lower_bound(X,X+xtot,left[i])-X; right[i]=lower_bound(X,X+xtot,right[i])-X; down[i]=lower_bound(Y,Y+ytot,down[i])-Y; up[i]=lower_bound(Y,Y+ytot,up[i])-Y; } int ans=0,now; for(i=1;i<xtot;++i){ memset(delta,0,sizeof(delta)); for(j=0;j<N;++j) if(left[j]<i&&right[j]>=i){ delta[down[j]]+=1; delta[up[j]]+=-1; } now=0; for(j=0;j<ytot;++j){ now+=delta[j]; if(!now&&delta[j]) ans+=(X[i]-X[i-1])<<1; } } for(i=1;i<ytot;++i){ memset(delta,0,sizeof(delta)); for(j=0;j<N;++j) if(down[j]<i&&up[j]>=i){ delta[left[j]]+=1; delta[right[j]]+=-1; } now=0; for(j=0;j<xtot;++j){ now+=delta[j]; if(!now&&delta[j]) ans+=(Y[i]-Y[i-1])<<1; } } printf("%d",ans); }
cogs859数列
题目大意：给定一个长度为n的数列，求这样的三个元素 ai,aj,ak 的个数，满足 ai<aj>ak，且 i<j<k。
思路：这道题比较简单，一看到的时候，用暴力的线段树做，得了80分，有点可惜。后来改进了思路，利用了题目中一个很好地条件（ai<=32767），这样的话就可以将线段树的结点表示这些整数，区间求和，维护两次线段树就可以了，最后将一个数两边比它小的个数相乘，就得到了正确结果。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; long long tree[200000]={0},minl[50001]={0},minr[50001]={0},a[50001]={0}; void insert(int i,int l,int r,int aa) { int mid; if (l==r) { ++tree[i]; return; } mid=(l+r)/2; if (aa<=mid) insert(i*2,l,mid,aa); else insert(i*2+1,mid+1,r,aa); tree[i]=tree[i*2]+tree[i*2+1]; } long long work(int i,int l,int r,int aa,int b) { long long ans=0; int mid; if (aa<=l&&r<=b) return tree[i]; mid=(l+r)/2; if (aa<=mid) ans+=work(i*2,l,mid,aa,b); if (b>mid) ans+=work(i*2+1,mid+1,r,aa,b); return ans; } int main() { freopen("queueb.in","r",stdin); freopen("queueb.out","w",stdout); int n,i,j; long long ans=0; scanf("%d",&n); for (i=1;i<=n;++i) { scanf("%lld",&a[i]); a[i]+=2; } for (i=1;i<=n;++i) { insert(1,1,32769,a[i]); if (i>1) minl[i]=work(1,1,32769,1,a[i]-1); } memset(tree,0,sizeof(tree)); for (i=n;i>=1;--i) { insert(1,1,32769,a[i]); if (i<n) minr[i]=work(1,1,32769,1,a[i]-1); if (i>1) ans+=minl[i]*minr[i]; } printf("%lld ",ans); fclose(stdin); fclose(stdout); }
cogs1260三元数对
题目大意：给定一个长度为n的数列，求这样的三个元素 ai,aj,ak 的个数，满足 ai<aj<ak，且 i<j<k。
思路：和上一题相同，只是要求右半段比它大的值。因为这一题的ai是longint，而n只有30000，所以就需要离散化一下，就能保证ai也在30000以内了（适当的+1，所以就会稍微大一点）。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; long long tree[200000]={0},minl[30001]={0},maxr[30001]={0}; int a[30001]={0},c[30001]={0}; void insert(int i,int l,int r,int aa) { int mid; if (l==r) { ++tree[i]; return; } mid=(l+r)/2; if (aa<=mid) insert(i*2,l,mid,aa); else insert(i*2+1,mid+1,r,aa); tree[i]=tree[i*2]+tree[i*2+1]; } long long work(int i,int l,int r,int aa,int b) { long long ans=0; int mid; if (aa<=l&&r<=b) return tree[i]; mid=(l+r)/2; if (aa<=mid) ans+=work(i*2,l,mid,aa,b); if (b>mid) ans+=work(i*2+1,mid+1,r,aa,b); return ans; } int main() { freopen("three.in","r",stdin); freopen("three.out","w",stdout); int n,i,j,size,maxn=0; long long ans=0; scanf("%d",&n); for (i=1;i<=n;++i) { scanf("%d",&a[i]); c[i]=a[i]; } sort(c+1,c+n+1); size=unique(c+1,c+n+1)-c-1; for (i=1;i<=n;++i) { a[i]=upper_bound(c+1,c+size+1,a[i])-c; maxn=max(a[i],maxn); } ++maxn; for (i=1;i<=n;++i) { insert(1,1,maxn,a[i]); minl[i]=work(1,1,maxn,1,a[i]-1); } memset(tree,0,sizeof(tree)); for (i=n;i>=1;--i) { insert(1,1,maxn,a[i]); maxr[i]=work(1,1,maxn,a[i]+1,maxn); ans+=minl[i]*maxr[i]; } printf("%lld",ans); fclose(stdin); fclose(stdout); }
cogs1212奶牛排队
题目大意：找一段区间满足左右端点分别为最小最大值，且中间没有一头牛的高度和端点处的一样。
思路：用线段树维护最大最小值，使最大值尽量靠左，且最小值尽量靠右。然后用深搜找一个区间，若最大值的下标==最小值的下标，就return；若最大值下标<最小值下标，则搜（l,lmax）(lmax+1,lmin-1)(lmin,r)；若最大值下标>最小值小标，更新ans，然后继续搜（l,lmin-1）(lmax+1,r)。
（一开始wa了很久，就是因为没有初始化。。。）
#include<iostream> #include<cstdio> using namespace std; struct use{ int maxn,minn,pmax,pmin; }tree[400000]; int a[100001]={0},ans=0,n; void build(int i,int l,int r) { int mid; if (l==r) { tree[i].maxn=tree[i].minn=a[l]; tree[i].pmax=tree[i].pmin=l; return; } mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); if (tree[i*2].maxn>=tree[i*2+1].maxn) { tree[i].maxn=tree[i*2].maxn;tree[i].pmax=tree[i*2].pmax; } else { tree[i].maxn=tree[i*2+1].maxn;tree[i].pmax=tree[i*2+1].pmax; } if (tree[i*2].minn<tree[i*2+1].minn) { tree[i].minn=tree[i*2].minn;tree[i].pmin=tree[i*2].pmin; } else { tree[i].minn=tree[i*2+1].minn;tree[i].pmin=tree[i*2+1].pmin; } } struct use work(int i,int l,int r,int aa,int b) { int mid; struct use ans1,ans2,ans3; ans1.maxn=ans2.maxn=-2100000000;ans1.pmax=ans2.pmax=2100000000; ans1.minn=ans2.minn=2100000000;ans1.pmin=ans2.pmin=0; if (aa<=l&&r<=b) return tree[i]; mid=(l+r)/2; if (aa<=mid) ans1=work(i*2,l,mid,aa,b); if (b>mid) ans2=work(i*2+1,mid+1,r,aa,b); if (ans1.maxn>=ans2.maxn) { ans3.maxn=ans1.maxn;ans3.pmax=ans1.pmax; } else { ans3.maxn=ans2.maxn;ans3.pmax=ans2.pmax; } if (ans1.minn<ans2.minn) { ans3.minn=ans1.minn;ans3.pmin=ans1.pmin; } else { ans3.minn=ans2.minn;ans3.pmin=ans2.pmin; } return ans3; } void dfs(int l,int r) { struct use aa,a1,a2; int d; if (r<=l) return; d=r-l+1; if (d<=ans) return; aa=work(1,1,n,l,r); if (aa.pmax==aa.pmin) return; if (aa.maxn==aa.minn) return; if (aa.pmax>aa.pmin) { ans=max(ans,aa.pmax-aa.pmin+1); dfs(l,aa.pmin-1); dfs(aa.pmax+1,r); } if (aa.pmax<aa.pmin) { dfs(l,aa.pmax); dfs(aa.pmax+1,aa.pmin-1); dfs(aa.pmin,r); } } int main() { freopen("tahort.in","r",stdin); freopen("tahort.out","w",stdout); int i,j; scanf("%d",&n); for (i=1;i<=n;++i) scanf("%d",&a[i]); build(1,1,n); dfs(1,n); if (ans==1) ans=2; printf("%d ",ans); fclose(stdin); fclose(stdout); }
cogs1543最优挤奶法
题目大意：给一定机器和他们的产奶量，求d天最多产奶量的和，每天都可以更改一个机器的产奶量。要求是相邻的两台机器不能同时开。
思路：本来想用tree一个数组保存这个区间的最大和，可是后来发现，这样的局部最优不能带来整体最优，所以一个新的算法就诞生了。保存这个区间取不取左右端点时的最大和，然后每次都对一个区间的四种状态进行更新（写了很牛的三个取最大值），然后没有查询的求和就可以了
#include<iostream> #include<cstdio> using namespace std; struct use{ long long c1,c2,c3,c4; }tree[160000]={0}; int a[40001]={0}; void updata(int i) { tree[i].c1=max(tree[i*2].c1+tree[i*2+1].c1,max(tree[i*2].c1+tree[i*2+1].c4,tree[i*2].c3+tree[i*2+1].c1)); tree[i].c2=max(tree[i*2].c2+tree[i*2+1].c3,max(tree[i*2].c4+tree[i*2+1].c2,tree[i*2].c4+tree[i*2+1].c3)); tree[i].c3=max(tree[i*2].c1+tree[i*2+1].c2,max(tree[i*2].c1+tree[i*2+1].c3,tree[i*2].c3+tree[i*2+1].c3)); tree[i].c4=max(tree[i*2].c4+tree[i*2+1].c4,max(tree[i*2].c2+tree[i*2+1].c1,tree[i*2].c4+tree[i*2+1].c1)); } void build(int i,int l,int r) { int mid; if (l==r) { tree[i].c2=a[l]; return; } mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); updata(i); } void insert(int i,int l,int r,int x,int y) { int mid; if (l==r) { tree[i].c2=y; tree[i].c1=tree[i].c3=tree[i].c4=0; return; } mid=(l+r)/2; if (x<=mid) insert(i*2,l,mid,x,y); else insert(i*2+1,mid+1,r,x,y); updata(i); } int main() { freopen("optmilk.in","r",stdin); freopen("optmilk.out","w",stdout); int i,j,n,k,d,m; long long ans=0,sum; scanf("%d%d",&n,&d); for (i=1;i<=n;++i) scanf("%d",&a[i]); build(1,1,n); for (i=1;i<=d;++i) { scanf("%d%d",&k,&m); insert(1,1,n,k,m); sum=max(tree[1].c1,max(tree[1].c2,max(tree[1].c3,tree[1].c4))); ans+=sum; } printf("%lld ",ans); fclose(stdin); fclose(stdout); }
cogs1829普通平衡树
题目大意：支持插入数x、删除数x、查找数x排名、查找排名为x的数、找数x的前驱、后继。
思路：看到题目和数据范围，很自然的想到了离散化，弄一个映射一样的东西，方便由离散化后的数找回原数。然后就是对离散化之后的整数建树了，每个区间保存有多少个数、最右面的和最左面的数在线段树中的下标（即离散化之后的数）。然后就是写插入和删除了，这里是单点修改（+1||-1）。查找数x的排名可以用1~x-1的区间求和+1来做（一开始这里读错了题，wa了一半，对于一个数x，若插入多次就当多个数看待，但是找到排名最小的输出）。查找排名为x的数可以借用以前约瑟夫问题的思路，先看左子树、再看右子树，决定去哪边找，若去右子树找还要减去左子树的个数。找数x的前驱和后继可以用一个函数，用结构体返回，利用tree里面的值，直接找。
这道题目综合了常见的线段树的各种操作，本身题目不难懂（虽然我一开始理解错了题意），但多种操作的组合很容易出现错误，这就要求对线段树又清晰地认识和体会。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct use{ int sum,maxn,minn; }tree[400000]={0}; struct use1{ int kind,num; }a[100001]; int cc[100001]={0},dd[100001]={0}; void updata(int i) { tree[i].sum=tree[i*2].sum+tree[i*2+1].sum; if (tree[i*2+1].maxn==0) tree[i].maxn=tree[i*2].maxn; else tree[i].maxn=tree[i*2+1].maxn; if (tree[i*2].minn==0) tree[i].minn=tree[i*2+1].minn; else tree[i].minn=tree[i*2].minn; } void insert(int i,int l,int r,int x,int y) { int mid; if (l==r) { tree[i].sum+=y; tree[i].maxn=tree[i].minn=l; if (tree[i].sum==0) { tree[i].maxn=tree[i].minn=0; } return; } mid=(l+r)/2; if (x<=mid) insert(i*2,l,mid,x,y); else insert(i*2+1,mid+1,r,x,y); updata(i); } int work1(int i,int l,int r,int x,int y) { int mid,ans=0; if (x<=l&&r<=y) return tree[i].sum; mid=(l+r)/2; if (x<=mid) ans+=work1(i*2,l,mid,x,y); if (y>mid) ans+=work1(i*2+1,mid+1,r,x,y); return ans; } int work2(int i,int l,int r,int x) { int mid; if (l==r) return l; mid=(l+r)/2; if (x<=tree[i*2].sum) return work2(i*2,l,mid,x); else return work2(i*2+1,mid+1,r,x-tree[i*2].sum); } struct use work(int i,int l,int r,int x,int y) { int mid; struct use ans1,ans2,ans; ans1.maxn=ans1.minn=ans2.maxn=ans2.minn=0; if (x<=l&&r<=y) return tree[i]; mid=(l+r)/2; if (x<=mid) ans1=work(i*2,l,mid,x,y); if (y>mid) ans2=work(i*2+1,mid+1,r,x,y); if (ans2.maxn==0) ans.maxn=ans1.maxn; else ans.maxn=ans2.maxn; if (ans1.minn==0) ans.minn=ans2.minn; else ans.minn=ans1.minn; return ans; } int main() { freopen("phs.in","r",stdin); freopen("phs.out","w",stdout); int n,opt,x,i,j,totc=0,size,ans1; struct use ans; scanf("%d",&n); for (i=1;i<=n;++i) { scanf("%d%d",&a[i].kind,&a[i].num); if (a[i].kind!=4) { ++totc; cc[totc]=a[i].num; } } sort(cc+1,cc+totc+1); size=unique(cc+1,cc+totc+1)-cc-1; for (i=1;i<=n;++i) { if (a[i].kind!=4) { opt=a[i].num; a[i].num=upper_bound(cc+1,cc+size+1,a[i].num)-cc-1; dd[a[i].num]=opt; } } for (i=1;i<=n;++i) { if (a[i].kind==1) insert(1,1,size,a[i].num,1); if (a[i].kind==2) insert(1,1,size,a[i].num,-1); if (a[i].kind==3) { if (a[i].num==1) ans1=1; else ans1=work1(1,1,size,1,a[i].num-1)+1; printf("%d ",ans1); } if (a[i].kind==4) { ans1=work2(1,1,size,a[i].num); printf("%d ",dd[ans1]); } if (a[i].kind==5) { ans=work(1,1,size,1,a[i].num-1); printf("%d ",dd[ans.maxn]); } if (a[i].kind==6) { ans=work(1,1,size,a[i].num+1,size); printf("%d ",dd[ans.minn]); } } fclose(stdin); fclose(stdout); }
cogs3032摆放球
题目大意：有n个橱窗，操作m次，每次放或拿一个球，放的时候要求使球离最近的球尽量远，拿的时候告诉球的编号。
思路：一开始竟然没有思路，后来想了想，这种操作也只有线段树能完成了。保存这个区间中最长的区间以及左右端点，和左右端点延伸的最长区间，然后每次插入的时候比较左右端点的长度和中间最长的长度/2（如果长度为偶数就-1），找到大的并且靠前的插入，就可以了。但是，这里有一个问题，就是对于一个区间长度为1、2的他们视为相同的区间，即如果长度为1在前面的话就放到长度为1的里面，然后就能a了这道题了。我们可以用映射的思想把编号和线段树中的位置对应下来。
这道题唯一仁慈的就是单点修改。
#include<iostream> #include<cstdio> using namespace std; struct use{ int ls,rs,lo,ll,rr,lls,rrs; }tree[1000000]; int pos[1000001]={0}; void updata(int i,int l,int r) { int mid; mid=(l+r)/2; tree[i].ls=tree[i*2].ls;tree[i].rs=tree[i*2+1].rs; tree[i].lo=tree[i*2].lo;tree[i].ll=tree[i*2].ll;tree[i].rr=tree[i*2].rr; tree[i].lls=tree[i*2].lls;tree[i].rrs=tree[i*2+1].rrs; if ((tree[i*2+1].ls+tree[i*2].rs+1)/2>(tree[i].lo+1)/2) { tree[i].lo=tree[i*2+1].ls+tree[i*2].rs; if (tree[i*2].rs>0) tree[i].ll=tree[i*2].rrs; else tree[i].ll=mid+1; if (tree[i*2+1].ls>0) tree[i].rr=tree[i*2+1].lls; else tree[i].rr=mid; } if ((tree[i*2+1].lo+1)/2>(tree[i].lo+1)/2) { tree[i].lo=tree[i*2+1].lo; tree[i].ll=tree[i*2+1].ll;tree[i].rr=tree[i*2+1].rr; } if (tree[i*2].ls==mid-l+1) { if (tree[i*2+1].ls>0) { tree[i].ls=tree[i].ls+tree[i*2+1].ls; tree[i].lls=tree[i*2+1].lls; } else tree[i].lls=mid; } if (tree[i*2+1].rs==r-mid) { if (tree[i*2].rs>0) { tree[i].rs=tree[i].rs+tree[i*2].rs; tree[i].rrs=tree[i*2].rrs; } else tree[i].rrs=mid+1; } } void build(int i,int l,int r) { int mid; if (l==r) { tree[i].ls=tree[i].rs=tree[i].lo=1; tree[i].ll=tree[i].rr=tree[i].lls=tree[i].rrs=l; return; } mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); updata(i,l,r); } void insert(int i,int l,int r,int x) { int mid; if (l==r) { tree[i].ls=tree[i].rs=tree[i].lo=0; tree[i].lls=tree[i].ll=tree[i].rrs=tree[i].rr=l; return; } mid=(l+r)/2; if (x<=mid) insert(i*2,l,mid,x); else insert(i*2+1,mid+1,r,x); updata(i,l,r); } void del(int i,int l,int r,int x) { int mid; if (l==r) { tree[i].ls=tree[i].rs=tree[i].lo=1; tree[i].lls=tree[i].rrs=tree[i].ll=tree[i].rr=l; return; } mid=(l+r)/2; if (x<=mid) del(i*2,l,mid,x); else del(i*2+1,mid+1,r,x); updata(i,l,r); } int main() { int n,m,t,i,j,kind,a,b,c; scanf("%d%d",&n,&m); build(1,1,n); for (i=1;i<=m;++i) { scanf("%d%d",&kind,&t); if (kind==1) { a=tree[1].ls-1;b=tree[1].lo/2;c=tree[1].rs-1; if (tree[1].lo%2==0) --b; if (a>=b&&a>=c) { insert(1,1,n,1); pos[t]=1; } if (b>a&&b>=c) { pos[t]=tree[1].ll+b; insert(1,1,n,tree[1].ll+b); } if (c>a&&c>b) { insert(1,1,n,n); pos[t]=n; } printf("%d ",pos[t]); } else { del(1,1,n,pos[t]); pos[t]=0; } } }
某个大神的模拟题T3 timer
题目大意：求n个元素中的k元逆序对（k个单减的元素），n个元素不重复。
思路：每个位置开一个k大小的数组，将数字排序后从小到大插入线段树，每次插入的值（一个数组）由这个位置后面的区间和（数组对应下标的和）平移1位（因为对于这个元素，之前逆序对的长度加了1）。最后答案就是整个线段树k位置的和。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxnode 100005 #define p 1000000007 using namespace std; struct use{ long long dp[15]; void init(){memset(dp,0,sizeof(dp));} }tree[maxnode*4]={0}; struct uu{ int num,po; }ai[maxnode]={0}; int k; int my_comp(const uu x,const uu y){return (x.num<y.num);} void updata(int i) { int j; for (j=0;j<=k;++j) tree[i].dp[j]=(tree[i*2].dp[j]+tree[i*2+1].dp[j])%p; } use task(int i,int l,int r,int ll,int rr) { int mid,j; use ans1,ans2; if (ll<=l&&r<=rr) return tree[i]; mid=(l+r)/2;ans1.init();ans2.init(); if (ll<=mid) ans1=task(i*2,l,mid,ll,rr); if (rr>mid) ans2=task(i*2+1,mid+1,r,ll,rr); for (j=1;j<=k;++j) ans1.dp[j]=(ans1.dp[j]+ans2.dp[j])%p; return ans1; } void tch(int i,int l,int r,int x,use y) { int mid; if (l==r){tree[i]=y;return;} mid=(l+r)/2; if (x<=mid) tch(i*2,l,mid,x,y); else tch(i*2+1,mid+1,r,x,y); updata(i); } int main() { freopen("timer.in","r",stdin); freopen("timer.out","w",stdout); int n,m,i,j; use xx; scanf("%d%d",&n,&k); if (k==1) printf("0 "); else { for (i=1;i<=n;++i) { scanf("%d",&ai[i].num);ai[i].po=i; } sort(ai+1,ai+n+1,my_comp); for (i=1;i<=n;++i) { if (ai[i].po<n) { xx=task(1,1,n,ai[i].po+1,n); for (j=k;j>=2;--j) xx.dp[j]=xx.dp[j-1]; } else xx.init(); xx.dp[1]=1; tch(1,1,n,ai[i].po,xx); } printf("%I64d ",tree[1].dp[k]); } fclose(stdin); fclose(stdout); }
bzoj1018 SHOI堵塞的交通
题目大意：2×c的网格，给出一些修改：使相邻格子联通或者堵塞，还有询问两点间的联通状况。
思路：线段树维护一个区间四个头互相连通的关系，这里的关系只是借助区间内部边联通的情况。在询问中，还要讨论通过外部联通的情况，取c小的一个为前，分类讨论：1）两个都在第一列；2）两个都在第二列；3）两个一上一下；4）两个一下一上。每一种情况里有四种联通的情况分类（这里很容易漏掉，一定要十分注意）。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxnode 100005 using namespace std; struct use{ bool updown,self[3],luru,ldrd,lurd,ldru,luld,rurd; void init(){luru=ldrd=lurd=ldru=luld=rurd=false;} }tree[maxnode*4]={false}; char ss[10]; int c; void change(int i) { if (tree[i].updown) tree[i].lurd=tree[i].ldru=tree[i].luld=tree[i].rurd=true; else tree[i].lurd=tree[i].ldru=tree[i].luld=tree[i].rurd=false; } use updata(use x1,use x2) { use ans;ans.init(); ans.self[1]=x2.self[1];ans.self[2]=x2.self[2]; if ((x1.luru&&x1.self[1]&&x2.luru)||(x1.lurd&&x1.self[2]&&x2.ldru)) ans.luru=true; if ((x1.ldrd&&x1.self[2]&&x2.ldrd)||(x1.ldru&&x1.self[1]&&x2.lurd)) ans.ldrd=true; if ((x1.luru&&x1.self[1]&&x2.lurd)||(x1.lurd&&x1.self[2]&&x2.ldrd)) ans.lurd=true; if ((x1.ldrd&&x1.self[2]&&x2.ldru)||(x1.ldru&&x1.self[1]&&x2.luru)) ans.ldru=true; if ((x1.luld)||(x1.luru&&x1.self[1]&&x2.luld&&x1.self[2]&&x1.ldrd)) ans.luld=true; if ((x2.rurd)||(x2.luru&&x1.self[1]&&x1.rurd&&x1.self[2]&&x2.ldrd)) ans.rurd=true; return ans; } void build(int i,int l,int r) { int mid; if (l==r){tree[i].luru=tree[i].ldrd=true;return;} mid=(l+r)/2;build(i*2,l,mid);build(i*2+1,mid+1,r); tree[i]=updata(tree[i*2],tree[i*2+1]); } void insh(int i,int l,int r,int x,int y,int kk) { int mid; if (l==r){tree[i].self[x]=kk;return;} mid=(l+r)/2; if (y<=mid) insh(i*2,l,mid,x,y,kk); else insh(i*2+1,mid+1,r,x,y,kk); tree[i]=updata(tree[i*2],tree[i*2+1]); } void insl(int i,int l,int r,int y,int kk) { int mid; if (l==r){tree[i].updown=kk;change(i);return;} mid=(l+r)/2; if (y<=mid) insl(i*2,l,mid,y,kk); else insl(i*2+1,mid+1,r,y,kk); tree[i]=updata(tree[i*2],tree[i*2+1]); } use ask(int i,int l,int r,int c1,int c2) { use ans1,ans2;int mid; bool f1,f2;f1=f2=false; if (c1<=l&&r<=c2) return tree[i]; mid=(l+r)/2; if (c1<=mid){ans1=ask(i*2,l,mid,c1,c2);f1=true;} if (c2>mid){ans2=ask(i*2+1,mid+1,r,c1,c2);f2=true;} if (f1&&f2) return updata(ans1,ans2); else { if (f1) return ans1; else return ans2; } } bool judge(int r1,int c1,int r2,int c2) { use x1,x2,x3; if (c1==c2&&r1==r2) return true; x1=ask(1,1,c,c1,c2);x2=ask(1,1,c,1,c1);x3=ask(1,1,c,c2,c); if (r1==r2) { if (r1==1) { if (x1.luru||(x1.ldrd&&x2.rurd&&x3.luld) ||(x2.rurd&&x1.ldru)||(x3.luld&&x1.lurd)) return true; } else { if (x1.ldrd||(x1.luru&&x2.rurd&&x3.luld) ||(x2.rurd&&x1.lurd)||(x3.luld&&x1.ldru)) return true; } } else { if (r1==1) { if (x1.lurd||(x2.rurd&&x1.ldrd)|| (x1.luru&&x3.luld)||(x2.rurd&&x3.luld&&x1.ldru)) return true; } else { if (x1.ldru||(x1.luru&&x2.rurd)|| (x1.ldrd&&x3.luld)||(x2.rurd&&x3.luld&&x1.lurd)) return true; } } return false; } int main() { int i,j,r1,c1,r2,c2; scanf("%d",&c);build(1,1,c); while(scanf("%s",&ss)==1) { if (ss[0]!='E'&&ss[0]!='C'&&ss[0]!='O'&&ss[0]!='A') continue; if (ss[0]=='E') break; scanf("%d%d%d%d",&r1,&c1,&r2,&c2); if (ss[0]=='C') { if (r1==r2) insh(1,1,c,r1,min(c1,c2),0); else insl(1,1,c,c1,0); } if (ss[0]=='O') { if (r1==r2) insh(1,1,c,r1,min(c1,c2),1); else insl(1,1,c,c1,1); } if (ss[0]=='A') { if (c1>c2) {swap(r1,r2);swap(c1,c2);} if(judge(r1,c1,r2,c2)) printf("Y "); else printf("N "); } } }
bzoj1858 序列操作
题目大意：给定一个0/1序列，支持区间覆盖、反转、查询1个数、查询1最长连续长度。
思路：线段树维护区间0、1个数，左右最长0、1连续长度，整个区间的最长0、1连续长度，反转和覆盖标记，区间长度。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxnode 100005 using namespace std; struct use{ int siz[2],lm[2],rm[2],mm[2],rev[2],len; void init() { siz[0]=siz[1]=lm[0]=lm[1]=0; rm[0]=rm[1]=mm[0]=mm[1]=len=0; } }tree[maxnode*4]={0}; int ai[maxnode]={0}; use updata(use l,use r) { use x;int i;x.len=l.len+r.len; x.rev[0]=-1;x.rev[1]=0; for (i=0;i<=1;++i) { x.siz[i]=l.siz[i]+r.siz[i]; if (l.lm[i]==l.len) x.lm[i]=l.lm[i]+r.lm[i]; else x.lm[i]=l.lm[i]; if (r.rm[i]==r.len) x.rm[i]=l.rm[i]+r.rm[i]; else x.rm[i]=r.rm[i]; x.mm[i]=max(l.mm[i],max(r.mm[i],l.rm[i]+r.lm[i])); } return x; } void getrev0(use &x,int k) { x.rev[0]=k;x.rev[1]=0; x.siz[k]=x.lm[k]=x.rm[k]=x.mm[k]=x.len; x.siz[k^1]=x.lm[k^1]=x.rm[k^1]=x.mm[k^1]=0; } void getrev1(use &x) { if (x.rev[0]!=-1) { int k=x.rev[0];x.siz[k]=x.lm[k]=x.rm[k]=x.mm[k]=0; x.rev[0]^=1;k^=1;x.siz[k]=x.lm[k]=x.rm[k]=x.mm[k]=x.len; } else { swap(x.siz[0],x.siz[1]);swap(x.lm[0],x.lm[1]); swap(x.rm[0],x.rm[1]);swap(x.mm[0],x.mm[1]); x.rev[1]^=1; } } void pushdown(int i) { if (tree[i].rev[0]>-1) { getrev0(tree[i*2],tree[i].rev[0]); getrev0(tree[i*2+1],tree[i].rev[0]); tree[i].rev[0]=-1; } if (tree[i].rev[1]) { getrev1(tree[i*2]);getrev1(tree[i*2+1]); tree[i].rev[1]=0; } } void build(int i,int l,int r) { if (l==r) { tree[i].lm[ai[l]]=tree[i].rm[ai[l]]=tree[i].mm[ai[l]]=1; tree[i].siz[ai[l]]=tree[i].len=1;tree[i].rev[0]=-1;return; } int mid=(l+r)/2; build(i*2,l,mid);build(i*2+1,mid+1,r); tree[i]=updata(tree[i*2],tree[i*2+1]); } void tch(int i,int l,int r,int ll,int rr,int k) { if (ll<=l&&r<=rr){getrev0(tree[i],k);return;} int mid=(l+r)/2;pushdown(i); if (ll<=mid) tch(i*2,l,mid,ll,rr,k); if (rr>mid) tch(i*2+1,mid+1,r,ll,rr,k); tree[i]=updata(tree[i*2],tree[i*2+1]); } void trev(int i,int l,int r,int ll,int rr) { if (ll<=l&&r<=rr){getrev1(tree[i]);return;} int mid=(l+r)/2;pushdown(i); if (ll<=mid) trev(i*2,l,mid,ll,rr); if (rr>mid) trev(i*2+1,mid+1,r,ll,rr); tree[i]=updata(tree[i*2],tree[i*2+1]); } int task(int i,int l,int r,int ll,int rr) { if (ll<=l&&r<=rr) return tree[i].siz[1]; int mid=(l+r)/2;int sum=0;pushdown(i); if (ll<=mid) sum+=task(i*2,l,mid,ll,rr); if (rr>mid) sum+=task(i*2+1,mid+1,r,ll,rr); return sum; } use mask(int i,int l,int r,int ll,int rr) { if (ll<=l&&r<=rr) return tree[i]; int mid=(l+r)/2;use x1,x2;pushdown(i); x1.init();x2.init(); if (ll<=mid) x1=mask(i*2,l,mid,ll,rr); if (rr>mid) x2=mask(i*2+1,mid+1,r,ll,rr); return updata(x1,x2); } int main() { int n,m,i,j,l,r,opt; scanf("%d%d",&n,&m); for (i=1;i<=n;++i) scanf("%d",&ai[i]); build(1,1,n); for (i=1;i<=m;++i) { scanf("%d%d%d",&opt,&l,&r);++l;++r; if (opt<=1) tch(1,1,n,l,r,opt); if (opt==2) trev(1,1,n,l,r); if (opt==3) printf("%d ",task(1,1,n,l,r)); if (opt==4) {use x=mask(1,1,n,l,r);printf("%d ",x.mm[1]);} } }
bzoj3333 排队计划（！！！）
题目大意：一个序列，每次选一个位置p，把它后面所有小于等于它的数取出来，排升序之后放回这些空位置，求每次操作后逆序对的个数。
思路：我们统计出以所有位置开始的逆序对的个数，每次操作就是看p到n的区间内，一次一次取最小的直到比p位置上的原数大为止，每次给答案减去查出来最小值的位置上那个逆序对的个数，再把最小值赋成正无穷就可以了，复杂度总共nlogn。这样做的正确性在于：考虑一次操作p，p之前的位置逆序对什么的都不会影响，如果p之后能选中的位置，那么它后面一定没有它的逆序对了；如果没选中的话，它的逆序对个数在操作后不会变。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxnode 500005 #define inf 2000000000LL #define LL long long using namespace std; struct use{ int num,sum,po,pm; void init(){ num=inf;sum=po=pm=0; } }tree[maxnode*4]={0},hi[maxnode]={0}; int ai[maxnode]={0}; int cmp(const use &x,const use &y){return x.num==y.num?x.po<y.po:x.num<y.num;} use updata(use x1,use x2) { use ans; ans.po=x1.po+x2.po; if (x1.num<=x2.num){ ans.num=x1.num;ans.pm=x1.pm; } else{ ans.num=x2.num;ans.pm=x2.pm; } return ans; } int asks(int i,int l,int r,int ll,int rr) { int sum=0; if (ll<=l&&r<=rr) return tree[i].po; int mid=(l+r)/2; if (ll<=mid) sum+=asks(i*2,l,mid,ll,rr); if (rr>mid) sum+=asks(i*2+1,mid+1,r,ll,rr); return sum; } use askm(int i,int l,int r,int ll,int rr) { use x1,x2;x1.init();x2.init(); if (ll<=l&&r<=rr) return tree[i]; int mid=(l+r)/2; if (ll<=mid) x1=askm(i*2,l,mid,ll,rr); if (rr>mid) x2=askm(i*2+1,mid+1,r,ll,rr); return updata(x1,x2); } int askss(int i,int l,int r,int x) { if (l==r) return tree[i].sum; int mid=(l+r)/2; if (x<=mid) return askss(i*2,l,mid,x); else return askss(i*2+1,mid+1,r,x); } void ins(int i,int l,int r,int x,int y,int z) { if (l==r){ tree[i].num=y;tree[i].sum=z; tree[i].pm=l;tree[i].po=1;return; } int mid=(l+r)/2; if (x<=mid) ins(i*2,l,mid,x,y,z); else ins(i*2+1,mid+1,r,x,y,z); tree[i]=updata(tree[i*2],tree[i*2+1]); } void tch(int i,int l,int r,int x) { if (l==r){tree[i].num=inf;tree[i].sum=0;tree[i].pm=l;return;} int mid=(l+r)/2; if (x<=mid) tch(i*2,l,mid,x); else tch(i*2+1,mid+1,r,x); tree[i]=updata(tree[i*2],tree[i*2+1]); } int main() { int n,i,j,m;LL ans=0;use u;scanf("%d%d",&n,&m); for (i=1;i<=n;++i){ scanf("%d",&ai[i]);hi[i].num=ai[i];hi[i].po=i; } sort(hi+1,hi+n+1,cmp); for (i=1;i<=n;++i) { j=asks(1,1,n,hi[i].po,n); ans+=(LL)j;ins(1,1,n,hi[i].po,hi[i].num,j); }printf("%I64d ",ans); for (i=1;i<=m;++i) { scanf("%d",&j);u=askm(1,1,n,j,n); while(u.num<=ai[j]) { ans-=(LL)askss(1,1,n,u.pm); tch(1,1,n,u.pm); u=askm(1,1,n,j,n); } printf("%I64d ",ans); } }
bzoj3064 cpu监控
题目大意：求一段区间内最大值和历史最大值，支持区间加、区间覆盖操作。
思路：其实并不是可持久化，用普通的线段树各种维护是可以a的。
#include<iostream> #include<cstdio> #define ri -1<<31 using namespace std; struct use{ int maxn,pmaxn,add,padd,c,pc; }tree[400000]; int a[100001]={0}; char ch; void updata(int i) { tree[i].maxn=max(tree[i*2].maxn,tree[i*2+1].maxn); tree[i].pmaxn=max(tree[i*2].pmaxn,tree[i*2+1].pmaxn); } void pushdown(int i) { int j,son; for (j=0;j<=1;++j) { son=i*2+j; tree[son].pmaxn=max(tree[son].pmaxn,max(tree[i].pc,tree[son].maxn+tree[i].padd)); if (tree[son].c==ri) tree[son].padd=max(tree[son].padd,tree[son].add+tree[i].padd); else tree[son].pc=max(tree[son].pc,tree[son].c+tree[i].padd); if (tree[i].add) { if (tree[son].c!=ri) tree[son].c+=tree[i].add; else tree[son].add+=tree[i].add; tree[son].maxn+=tree[i].add; } if (tree[i].c!=ri) { tree[son].maxn=tree[son].c=tree[i].c; tree[son].add=0; } tree[son].pc=max(tree[son].pc,max(tree[son].c,tree[i].pc)); tree[son].padd=max(tree[son].padd,tree[son].add); } tree[i].padd=tree[i].add=0; tree[i].pc=tree[i].c=ri; } void build(int i,int l,int r) { int mid; tree[i].add=tree[i].padd=0; tree[i].c=tree[i].pc=ri; if (l==r) { tree[i].maxn=tree[i].pmaxn=a[l]; return; } mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); updata(i); } int ask(int i,int l,int r,int ll,int rr) { int mid,maxn; if (l!=r) pushdown(i); if (ll<=l&&r<=rr) { if (ch=='Q') return tree[i].maxn; else return tree[i].pmaxn; } mid=(l+r)/2;maxn=ri; if (ll<=mid) maxn=max(maxn,ask(i*2,l,mid,ll,rr)); if (rr>mid) maxn=max(maxn,ask(i*2+1,mid+1,r,ll,rr)); return maxn; } void work(int i,int l,int r,int ll,int rr,int cc) { int mid; if (l!=r) pushdown(i); if (ll<=l&&r<=rr) { if (ch=='P') { tree[i].maxn+=cc;tree[i].add+=cc;tree[i].padd+=cc; } else { tree[i].c=tree[i].pc=tree[i].maxn=cc; } if (tree[i].maxn>tree[i].pmaxn) tree[i].pmaxn=tree[i].maxn; return; } mid=(l+r)/2; if (ll<=mid) work(i*2,l,mid,ll,rr,cc); if (rr>mid) work(i*2+1,mid+1,r,ll,rr,cc); updata(i); } int main() { int t,i,j,e,x,y,z; scanf("%d",&t); for (i=1;i<=t;++i) scanf("%d",&a[i]); build(1,1,t); scanf("%d",&e); for (i=1;i<=e;++i) { while(scanf("%c",&ch)==1) if (ch>='A'&&ch<='Z') break; if (ch=='Q'||ch=='A') { scanf("%d%d",&x,&y); printf("%d ",ask(1,1,t,x,y)); } else { scanf("%d%d%d",&x,&y,&z); work(1,1,t,x,y,z); } } }
bzoj4293 Siano
题目大意：n个点有不同的升高速度，操作是某一个时间砍掉比某个高度高的部分，求这部分的和。
思路：对升高速度排序后，这个序列一定不降。所以就可以在线段树上区间覆盖、增减、查大于某一个数的最左位置、区间和，这里的pushdown有一些顺序。
注意：1）updata返回结构体的时候，相应的没有更新的位置要赋值；
2）如果操作中continue掉某次操作，要对一些全局用到的变量进行相应的更改（如这题中的la）。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long #define maxm 500005 using namespace std; struct use{ LL maxn,sum,del,y,ds; }tree[maxm*4]={0}; LL ai[maxm]={0}; use updata(use a,use b){ use c;c.maxn=max(a.maxn,b.maxn); c.sum=a.sum+b.sum;c.ds=a.ds+b.ds; c.del=0;c.y=-1; return c; } void build(int i,int l,int r){ if (l==r){tree[i].y=-1;tree[i].ds=ai[l];return;} int mid=(l+r)/2; build(i*2,l,mid);build(i*2+1,mid+1,r); tree[i]=updata(tree[i*2],tree[i*2+1]); } void paintx(int i,int l,int r,LL x){ tree[i].maxn+=x*ai[r];tree[i].sum+=tree[i].ds*x; tree[i].del+=x; } void pushdownx(int i,int l,int r){ if (!tree[i].del) return; int mid=(l+r)/2; paintx(i*2,l,mid,tree[i].del); paintx(i*2+1,mid+1,r,tree[i].del); tree[i].del=0; } void painty(int i,int l,int r,LL x){ tree[i].del=0;tree[i].maxn=x; tree[i].sum=x*(LL)(r-l+1);tree[i].y=x; } void pushdowny(int i,int l,int r){ if (tree[i].y==-1) return; int mid=(l+r)/2; painty(i*2,l,mid,tree[i].y);painty(i*2+1,mid+1,r,tree[i].y); tree[i].y=-1; } int askp(int i,int l,int r,LL x){ if (l==r) return l; int mid=(l+r)/2; pushdowny(i,l,r);pushdownx(i,l,r); if (tree[i*2].maxn>=x) return askp(i*2,l,mid,x); else return askp(i*2+1,mid+1,r,x); } LL asks(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr) return tree[i].sum; LL sum=0;int mid=(l+r)/2; if (ll<=mid) sum+=asks(i*2,l,mid,ll,rr); if (rr>mid) sum+=asks(i*2+1,mid+1,r,ll,rr); return sum; } void tch(int i,int l,int r,int ll,int rr,LL x){ if (ll<=l&&r<=rr){painty(i,l,r,x);return;} int mid=(l+r)/2; pushdowny(i,l,r);pushdownx(i,l,r); if (ll<=mid) tch(i*2,l,mid,ll,rr,x); if (rr>mid) tch(i*2+1,mid+1,r,ll,rr,x); tree[i]=updata(tree[i*2],tree[i*2+1]); } int main(){ int n,m,i,j;LL di,bi,la=0;scanf("%d%d",&n,&m); for (i=1;i<=n;++i) scanf("%I64d",&ai[i]); sort(ai+1,ai+n+1);build(1,1,n); for (i=1;i<=m;++i){ scanf("%I64d%I64d",&di,&bi);paintx(1,1,n,di-la); if (tree[1].maxn<bi){printf("0 ");la=di;continue;} j=askp(1,1,n,bi);la=di; printf("%I64d ",asks(1,1,n,j,n)-(LL)(n-j+1)*bi); tch(1,1,n,j,n,bi); } }
bzoj3339 Rmq Problem
题目大意：求一段区间的mex。
思路：离线+区间修改、单点查询。按左端点排序，先扫一遍算出1～i的mex，放入线段树，然后考虑l~r->l+1~r就是去掉ai[l]这个数之后，从i～ne[l]-1(下一个数为ai[l]的位置)比ai[l]大的都变为ai[l]就可以了。
（orz hzwer）
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxm 200005 using namespace std; struct use{ int l,r,po; }ask[maxm]={0}; int tree[maxm*4]={0},delta[maxm*4]={0},ai[maxm]={0},po[maxm]={0},ne[maxm]={0},bi[maxm]={0}, ans[maxm]={0}; bool used[maxm]={false}; int cmp(const use&x,const use&y){return x.l<y.l;} void build(int i,int l,int r){ if (l==r){tree[i]=bi[l];return;} int mid=(l+r)/2; build(i*2,l,mid);build(i*2+1,mid+1,r); } void pushdown(int i){ if (delta[i]<delta[0]){ delta[i*2]=min(delta[i*2],delta[i]); tree[i*2]=min(tree[i*2],delta[i*2]); delta[i*2+1]=min(delta[i*2+1],delta[i]); tree[i*2+1]=min(tree[i*2+1],delta[i*2+1]); delta[i]=delta[0]; } } void tch(int i,int l,int r,int ll,int rr,int x){ if (ll<=l&&r<=rr){ tree[i]=min(tree[i],x); delta[i]=min(delta[i],x);return; }pushdown(i); int mid=(l+r)/2; if (ll<=mid) tch(i*2,l,mid,ll,rr,x); if (rr>mid) tch(i*2+1,mid+1,r,ll,rr,x); } int task(int i,int l,int r,int x){ if (l==r) return tree[i]; int mid=(l+r)/2; pushdown(i); if (x<=mid) return task(i*2,l,mid,x); else return task(i*2+1,mid+1,r,x); } int main(){ int n,q,i,j;scanf("%d%d",&n,&q); for (i=1;i<=n;++i) scanf("%d",&ai[i]); for (i=0;i<maxm;++i) po[i]=n+1; for (i=n;i;--i){ne[i]=po[ai[i]];po[ai[i]]=i;} for (j=0,i=1;i<=n;++i){ used[ai[i]]=true; while(used[j]) ++j; bi[i]=j; }memset(tree,127,sizeof(tree)); build(1,1,n);memset(delta,127,sizeof(delta)); for (i=1;i<=q;++i){scanf("%d%d",&ask[i].l,&ask[i].r);ask[i].po=i;} sort(ask+1,ask+q+1,cmp);ask[0].l=1; for (i=1;i<=q;i=j){ for (j=ask[i-1].l;j<ask[i].l;++j) tch(1,1,n,j,ne[j]-1,ai[j]); j=i; while(j<=q&&ask[j].l==ask[i].l){ ans[ask[j].po]=task(1,1,n,ask[j].r);++j; } }for (i=1;i<=q;++i) printf("%d ",ans[i]); }
bzoj2962 序列操作
题目大意：给定一个数列，可以区间加、区间取反、区间内c个元素的乘积和。
思路：线段树维护。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxm 50005 #define up 20 #define p 19940417LL #define LL long long using namespace std; struct use{ LL fi[up+1],delta;int rev; void init(){memset(fi,0,sizeof(fi));delta=rev=0;} }tree[maxm*4]={0}; LL ai[maxm]={0},cc[maxm][up+1]={0},mi[maxm]={0}; char in(){ char ch=getchar(); while(true){ if (ch>='A'&&ch<='Z') return ch; ch=getchar(); } } use updata(use x,use y){ use ci;ci.init();int i,j,k; for (i=1;i<=up;++i){ ci.fi[i]=(x.fi[i]+y.fi[i])%p; for (j=1;j<i;++j) ci.fi[i]=(ci.fi[i]+x.fi[j]*y.fi[i-j]%p)%p; }return ci; } void build(int i,int l,int r){ if (l==r){tree[i].fi[1]=ai[l];return;} int mid=(l+r)>>1; build(i<<1,l,mid);build(i<<1|1,mid+1,r); tree[i]=updata(tree[i<<1],tree[i<<1|1]); } void paint(int i,int l,int r,LL x){ int j,k;LL xx; if (x==0){ tree[i].rev^=1;tree[i].delta=((p-tree[i].delta)%p+p)%p; for (j=1;j<=min(r-l+1,up);j+=2) tree[i].fi[j]=((p-tree[i].fi[j])%p+p)%p; }else{ x=(x%p+p)%p;tree[i].delta=((tree[i].delta+x)%p+p)%p; for (j=min(up,r-l+1);j;--j){ for (xx=x,k=j-1;k;--k){ tree[i].fi[j]=(tree[i].fi[j]+cc[r-l+1-k][j-k]*xx%p*tree[i].fi[k]%p)%p; xx=xx*x%p; }tree[i].fi[j]=(tree[i].fi[j]+cc[r-l+1][j]*xx%p)%p; } } } void pushdown(int i,int l,int r){ int mid=(l+r)>>1; if (tree[i].rev){ paint(i<<1,l,mid,0);paint(i<<1|1,mid+1,r,0); }if (tree[i].delta!=0){ paint(i<<1,l,mid,tree[i].delta); paint(i<<1|1,mid+1,r,tree[i].delta); }tree[i].rev=0;tree[i].delta=0; } void ins(int i,int l,int r,int ll,int rr,LL x){ if (ll<=l&&r<=rr){paint(i,l,r,x);return;} int mid=(l+r)>>1;pushdown(i,l,r); if (ll<=mid) ins(i<<1,l,mid,ll,rr,x); if (rr>mid) ins(i<<1|1,mid+1,r,ll,rr,x); tree[i]=updata(tree[i<<1],tree[i<<1|1]); } void rev(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr){paint(i,l,r,0);return;} int mid=(l+r)>>1;pushdown(i,l,r); if (ll<=mid) rev(i<<1,l,mid,ll,rr); if (rr>mid) rev(i<<1|1,mid+1,r,ll,rr); tree[i]=updata(tree[i<<1],tree[i<<1|1]); } use ask(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr) return tree[i]; int mid=(l+r)>>1;pushdown(i,l,r); use x1,x2;bool f1=false,f2=false; x1.init();x2.init(); if (ll<=mid){x1=ask(i<<1,l,mid,ll,rr);f1=true;} if (rr>mid){x2=ask(i<<1|1,mid+1,r,ll,rr);f2=true;} if (f1&&f2) return updata(x1,x2); else return (f1 ? x1 : x2); } int main(){ int n,q,i,j,a,b;LL c;char ch; scanf("%d%d",&n,&q); for (i=0;i<=n;++i) cc[i][0]=1; for (i=1;i<=n;++i) for (j=1;j<=20;++j) cc[i][j]=(cc[i-1][j-1]+cc[i-1][j])%p; for (i=1;i<=n;++i){scanf("%I64d",&ai[i]);ai[i]=(ai[i]%p+p)%p;} build(1,1,n); for (i=1;i<=q;++i){ if ((ch=in())=='I'){ scanf("%d%d%I64d",&a,&b,&c); c=(c%p+p)%p;if (c==0) continue; ins(1,1,n,a,b,c); }if (ch=='R'){ scanf("%d%d",&a,&b);rev(1,1,n,a,b); }if (ch=='Q'){ scanf("%d%d%d",&a,&b,&j); use ci=ask(1,1,n,a,b); printf("%I64d ",ci.fi[j]); } } }
bzoj3226 校门外的树
题目大意：支持对一些集合的操作，包括并、交、减（包括前减后和后减前）、异或（集合的异或表示只在一个集合中出现的元素）。
思路：用线段树维护每个小段选或者不选（可以把[1,1],(1，2),[2,2]这样的区间作为线段树的叶子）。并就是区间覆盖（y的为1），交可以看作!((!x)or(!y))，前减后可以看作区间覆盖（y的为0），后减前是(!x)andy，异或就是y区域取反（这个操作有点难想），所以线段树里维护区间覆盖和区间取反的标记就可以了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxm 600000 #define up 131070 using namespace std; struct use{ int len,s,dq,df; //dq 清0|1 df 取反 }t[maxm]; char s[maxm];int f[maxm],sl; int gn(int &i){ int x=0; while(i<sl&&(s[i]<'0'||s[i]>'9')) ++i; while(i<sl&&(s[i]>='0'&&s[i]<='9')){ x=x*10+s[i]-'0';++i; }return x; } use updata(use x,use y){ use c;c.len=x.len+y.len; c.s=x.s+y.s;c.dq=-1;c.df=0; return c; } void build(int i,int l,int r){ if (l==r){t[i]=(use){r-l+1,0,-1,0};return;} int mid=l+r>>1; build(i<<1,l,mid);build(i<<1|1,mid+1,r); t[i]=updata(t[i<<1],t[i<<1|1]); } void paintc(int i,int l,int r,int kk){//下传dq if (t[i].df) t[i].df=0;t[i].dq=kk; if (kk) t[i].s=t[i].len; else t[i].s=0; } void paintf(int i,int l,int r){//下传df if (t[i].dq>=0) t[i].dq^=1; else t[i].df^=1; t[i].s=t[i].len-t[i].s; } void pushdown(int i,int l,int r){ int mid=l+r>>1; if (t[i].dq>=0){ paintc(i<<1,l,mid,t[i].dq); paintc(i<<1|1,mid+1,r,t[i].dq); t[i].dq=-1; }if (t[i].df){ paintf(i<<1,l,mid);paintf(i<<1|1,mid+1,r); t[i].df=0; } } void tch(int i,int l,int r,int ll,int rr,int kk){ if (ll<=l&&r<=rr){paintc(i,l,r,kk);return;} int mid=l+r>>1;pushdown(i,l,r); if (ll<=mid) tch(i<<1,l,mid,ll,rr,kk); if (rr>mid) tch(i<<1|1,mid+1,r,ll,rr,kk); t[i]=updata(t[i<<1],t[i<<1|1]); } void qf(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr){paintf(i,l,r);return;} int mid=l+r>>1;pushdown(i,l,r); if (ll<=mid) qf(i<<1,l,mid,ll,rr); if (rr>mid) qf(i<<1|1,mid+1,r,ll,rr); t[i]=updata(t[i<<1],t[i<<1|1]); } void print(int i,int l,int r){ if (l==r){f[l]=t[i].s;return;} int mid=l+r>>1;pushdown(i,l,r); print(i<<1,l,mid);print(i<<1|1,mid+1,r); t[i]=updata(t[i<<1],t[i<<1|1]); } int main(){ int i,j,a,b,k1,k2;char c; build(1,0,up); while(gets(s)){ sl=strlen(s);if (sl==0) continue; for (i=0;i<sl&&(s[i]<'A'||s[i]>'Z');++i); c=s[i]; for (;i<sl&&(s[i]!='('&&s[i]!='[');++i); k1=(s[i]=='(');a=gn(i);b=gn(i); for (;i<sl&&(s[i]!=')'&&s[i]!=']');++i); k2=(s[i]==')'); a=a*2+k1;b=b*2-k2; if (a>b) continue; if (c=='U') tch(1,0,up,a,b,1); if (c=='I'||c=='C'){ if (c=='I') qf(1,0,up,0,up); k1=0;--a;++b;k2=up; if (k1<=a) tch(1,0,up,k1,a,1); if (b<=k2) tch(1,0,up,b,k2,1); qf(1,0,up,0,up); }if (c=='D') tch(1,0,up,a,b,0); if (c=='S') qf(1,0,up,a,b); }print(1,0,up); for (i=0;i<=up;i=j+1){ j=i;if (!f[i]) continue; while(j<up&&f[j+1]) ++j; printf("%c%d,%d%c ",i%2 ? '(' : '[',i/2,(j+1)/2,j%2 ? ')' : ']'); }if (!t[1].s) printf("empty set"); printf(" "); }
bzoj1227 虔诚的墓主人
题目大意：在网格内有一些树，以一个没有树的格子内同时上下左右各选k棵树组成十字架，求不同的十字架的个数。
思路：因为网格很大，所以离散化，逐行处理。线段树维护的是这一列到当前行时上面的棵数与下面的棵数的乘积。每一行中自左到右依次处理，两棵树之间对答案的贡献就是c[左边的树数][k]*c[右边的树数][k]*sigma(i=xl+1~xr-1)c[上边的树数][k]*c[下面的树数][k]，每一个位置处理过去之后线段树中相应的进行更改，边做边统计左右上下的棵树就可以了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxm 100005 #define up 15 #define LL long long #define p 2147483648LL using namespace std; struct use{int x,y;}ai[maxm]; LL c[maxm][up]={0},tr[maxm*4]={0}; int ri[maxm]={0},ui[maxm]={0},oi[maxm]={0},xi[maxm],yi[maxm]; int cmp(const use&x,const use&y){return (x.y==y.y ? x.x<y.x : x.y<y.y);} void pre(int n,int m){ int i,j,uu;c[0][0]=1LL; for (i=1;i<=n;++i){ c[i][0]=1LL;uu=min(i,m); for (j=1;j<=uu;++j) c[i][j]=(c[i-1][j]+c[i-1][j-1])%p; } } void tch(int i,int l,int r,int x,LL y){ if (l==r){tr[i]=y;return;} int mid=l+r>>1; if (x<=mid) tch(i<<1,l,mid,x,y); else tch(i<<1|1,mid+1,r,x,y); tr[i]=(tr[i<<1]+tr[i<<1|1])%p; } LL ask(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr) return tr[i]; int mid=l+r>>1;LL ci=0LL; if (ll<=mid) ci=(ci+ask(i<<1,l,mid,ll,rr))%p; if (rr>mid) ci=(ci+ask(i<<1|1,mid+1,r,ll,rr))%p; return ci; } int main(){ int n,m,i,j,t,w,k,sx,sy,x1,x2,li,y1;LL ans=0LL; scanf("%d%d%d",&n,&m,&w); for (i=1;i<=w;++i){ scanf("%d%d",&ai[i].x,&ai[i].y); xi[i]=ai[i].x;yi[i]=ai[i].y; }scanf("%d",&k);pre(w,k);sort(ai+1,ai+w+1,cmp); sort(xi+1,xi+w+1);sort(yi+1,yi+w+1); sx=unique(xi+1,xi+w+1)-xi-1; sy=unique(yi+1,yi+w+1)-yi-1; for (i=1;i<=w;++i){ ++ri[upper_bound(yi+1,yi+sy+1,ai[i].y)-yi-1]; ++ui[upper_bound(xi+1,xi+sx+1,ai[i].x)-xi-1]; }for (i=1;i<=w;i=j+1){ j=i;li=0; while(j<w&&ai[j+1].y==ai[i].y) ++j; y1=upper_bound(yi+1,yi+sy+1,ai[i].y)-yi-1; for (t=i;t<j;++t){ x1=upper_bound(xi+1,xi+sx+1,ai[t].x)-xi-1; x2=upper_bound(xi+1,xi+sx+1,ai[t+1].x)-xi-1; ++li; if (x1<x2-1) ans=(ans+c[li][k]*c[ri[y1]-li][k]%p*ask(1,1,sx,x1+1,x2-1)%p)%p; tch(1,1,sx,x1,c[(oi[x1]+=1)][k]*c[ui[x1]-oi[x1]][k]%p); }x1=upper_bound(xi+1,xi+sx+1,ai[j].x)-xi-1; tch(1,1,sx,x1,c[(oi[x1]+=1)][k]*c[ui[x1]-oi[x1]][k]%p); }printf("%I64d ",ans); }
bc67 the soldier of love
题目大意：给定n条线段，m组点，求对于每组点，至少覆盖一个点的线段数量。
思路：补集思想+线段树。线段树表示该下标是多少条线段的左端点。求一个点都不覆盖的线段数，对于对于每组点中的相邻点就是看作一条pi+1~pj-1的线段，记录是哪组的，然后对线段的右端点排序之后，从左到右扫一下（注意相同端点的时候先做线段的，再做点的），做线段的时候就是把左端点的位置+1，点的时候就是查询这段区间内的左端点的个数。最后答案就是n-ansi。注意加点的时候还要加左右边的。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 1000005 #define up 1000000 using namespace std; struct use{ int l,r,p; bool operator<(const use&x)const{ return (r==x.r ? p<x.p : r<x.r);} }ai[N]; int tr[N*4],ans[N]={0}; void tch(int i,int l,int r,int x){ if (l==r){++tr[i];return;} int mid=l+r>>1; if (x<=mid) tch(i<<1,l,mid,x); else tch(i<<1|1,mid+1,r,x); tr[i]=tr[i<<1]+tr[i<<1|1]; } int ask(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr) return tr[i]; int mid=l+r>>1,ci=0; if (ll<=mid) ci+=ask(i<<1,l,mid,ll,rr); if (rr>mid) ci+=ask(i<<1|1,mid+1,r,ll,rr); return ci; } int main(){ int n,m,k,i,j,x,la; while(scanf("%d%d",&n,&m)==2){ memset(tr,0,sizeof(tr)); for (i=1;i<=n;++i){ scanf("%d%d",&ai[i].l,&ai[i].r); ai[i].p=0; }for (i=1;i<=m;++i) ans[i]=n; for (i=1;i<=m;++i){ scanf("%d",&k);la=0; for (j=1;j<=k;++j){ scanf("%d",&x); if (x-1>la) ai[++n]=(use){la+1,x-1,i}; la=x; }if (x<up) ai[++n]=(use){x+1,up,i}; }sort(ai+1,ai+n+1); for (i=1;i<=n;++i){ if (ai[i].p) ans[ai[i].p]-=ask(1,1,up,ai[i].l,ai[i].r); else tch(1,1,up,ai[i].l); }for (i=1;i<=m;++i) printf("%d ",ans[i]); } }
bc67 merge
题目大意：一开始有n个集合，第i个是单元素集{i}，做n-1次合并操作，合并之后让最小的和最大的相遇（每次可以交换数轴上相邻两个元素，时间是差；如果交换的是最大最小值，只需要差的一半就可以相遇），求最小的相遇时间。
思路：假设一个集合中的最大最小值在a[j],a[j+1]之间相遇，那么时间就是max(a[j]-a[1],a[siz]-a[j+1])+(a[j+1]-a[j])/2=max(ci-a[1],a[n]-ci)(ci=(a[j]+a[j+1])/2)，这里的a[j],a[j+1]的中点一定是最接近a[1],a[siz]中点mid的那一组，所以可以在一个数据结构中查找mid的前驱后继，然后再找两边各一个区间，比出中点到mid的最小值，算出答案。
这里的合并有两种方法：
1）启发式合并，O(nlognlogn)，在hdu上tle了，数据结构可以用set，十分简洁。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<set> #define N 300005 #define LD double using namespace std; set<int> se[N]; int fa[N],siz[N]; int in(){ char ch=getchar();int x=0; while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar(); }return x;} int root(int x){return (fa[x]==x ? x : fa[x]=root(fa[x]));} int ab(int x){return (x>=0 ? x : -x);} int main(){ int i,j,n,u,v,t,x,y,a,b,mid,mn,ci;t=in(); set<int>::iterator it,it1,be,en; while(t--){ n=in(); for (i=1;i<=n;++i){fa[i]=i;se[i].clear();se[i].insert(i*2);siz[i]=1;} for (i=1;i<n;++i){ u=in();v=in(); u=root(u);v=root(v); if (siz[u]<siz[v])swap(u,v); fa[v]=u;siz[u]+=siz[v];en=se[v].end(); for (it=se[v].begin();it!=en;++it) se[u].insert(*it); se[v].clear();be=se[u].begin();en=se[u].end();--en; mid=(*be + *en)/2; it=it1=se[u].upper_bound(mid);y=*it; x=(*(--it));mn=ab(mid-(ci=(x+y)/2)); if (it!=be){ a=*(--it); if (ab(mid-(a+x)/2)<mn) mn=ab(mid-(ci=(a+x)/2)); }if (it1!=en){ b=*(++it1); if (ab(mid-(y+b)/2)<mn) mn=ab(mid-(ci=(y+b)/2)); }printf("%.1f ",(LD)max(ci- *be,*en - ci)/2.0); } } }
2）用权值线段树维护每一个点所在区间的最大最小值，合并的时候类似主席树，在线段树中查前驱后继的时候一定要考虑正确（比如查前驱：没有右儿子或者右儿子的最小值>x才去左区间找），O(nlogn)。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 300005 #define len 7000000 #define LD double using namespace std; struct use{ int l,r,lm,rm; void init(){l=r=rm=0;lm=N;} }tr[len]; int root[N],fa[N],siz[N],tot; int rool(int x){return (fa[x]==x ? x : fa[x]=rool(fa[x]));} int ab(int x){return (x>=0 ? x : -x);} void updata(int x){ tr[x].lm=min(tr[tr[x].l].lm,tr[tr[x].r].lm); tr[x].rm=max(tr[tr[x].l].rm,tr[tr[x].r].rm);} void tch(int &x,int l,int r,int y){ if (!x) tr[x=++tot].init(); if (l==r){tr[x].lm=tr[x].rm=y;return;} int mid=l+r>>1; if (y<=mid) tch(tr[x].l,l,mid,y); else tch(tr[x].r,mid+1,r,y); updata(x);} void uni(int &x,int &y,int l,int r){ if (!y) return; if (!x) {x=y;return;} int mid=l+r>>1; uni(tr[x].l,tr[y].l,l,mid); uni(tr[x].r,tr[y].r,mid+1,r); updata(x);} int pre(int i,int l,int r,int x){ if (l==r) return l; int mid=l+r>>1; if (!tr[i].r||(tr[i].r&&x<tr[tr[i].r].lm)) return pre(tr[i].l,l,mid,x); else return pre(tr[i].r,mid+1,r,x);} int suc(int i,int l,int r,int x){ if (l==r) return l; int mid=l+r>>1; if (!tr[i].l||(tr[i].l&&x>tr[tr[i].l].rm)) return suc(tr[i].r,mid+1,r,x); else return suc(tr[i].l,l,mid,x);} int main(){ int T,i,j,n,u,v,mid,ci,mn,be,en,x,y,a,b; scanf("%d",&T);tr[0].init(); while(T--){ scanf("%d",&n);tot=0; for (i=1;i<=n;++i){ fa[i]=i;siz[i]=1;root[i]=0; tch(root[i],1,n,i); }for (i=1;i<n;++i){ scanf("%d%d",&u,&v); u=rool(u);v=rool(v); if (siz[u]<siz[v]) swap(u,v); fa[v]=u;siz[u]+=siz[v]; uni(root[u],root[v],1,n); be=tr[root[u]].lm;en=tr[root[u]].rm; mid=(be+en)/2; x=pre(root[u],1,n,mid); y=suc(root[u],1,n,mid+1); mn=ab(be+en-(ci=x+y)); if (x!=be){ a=pre(root[u],1,n,x-1); if (ab(be+en-(a+x))<mn) mn=ab(be+en-(ci=a+x)); }if (y!=en){ b=suc(root[u],1,n,y+1); if (ab(be+en-(y+b))<mn) mn=ab(be+en-(ci=b+y)); }printf("%.1f ",(LD)max(en*2-ci,ci-2*be)/2.); } } }
bzoj3995 道路修建
题目大意：一个2行n列的网格，格上有边权，两种操作：修改某一条边权；查询l~r两行的最小生成树的权值。
思路：对于一个格子（包含四个点）有5种状态（本来是10种，但有一些在转移时是一样的，所以放在一起做；这5种分别是：左右两列都需要在外面相接，左或右任意一个或者必选哪个，格已经连通，然后相应的有17种转移）。注意：格已连通的时候有四种初始，四条边分别去掉的情况都可以。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long #define N 60005 #define inf 2100000000LL using namespace std; struct use{ LL vi[5]; void init(){for (int i=0;i<5;++i) vi[i]=inf;} }tr[N*4]; LL ed[3][N]; int map[5][5]={{-1,0,0,-1,3}, {0,1,2,3,4}, {-1,2,2,-1,4}, {0,3,-1,3,-1}, {2,4,-1,4,-1}}; char in(){ char ch=getchar(); while(ch<'A'||ch>'Z') ch=getchar(); return ch;} void paint(int i,int x){ tr[i].init(); tr[i].vi[0]=min(ed[0][x],ed[1][x]); tr[i].vi[1]=ed[0][x]+ed[1][x]; tr[i].vi[2]=min(ed[0][x],ed[1][x])+ed[2][x]; tr[i].vi[3]=min(ed[0][x],ed[1][x])+ed[2][x+1]; tr[i].vi[4]=min(ed[0][x]+ed[1][x]+min(ed[2][x],ed[2][x+1]), ed[2][x]+ed[2][x+1]+min(ed[0][x],ed[1][x]));} use updata(use x,use y){ use c;c.init();int i,j; for (i=0;i<5;++i) for (j=0;j<5;++j){ if (map[i][j]<0) continue; c.vi[map[i][j]]=min(c.vi[map[i][j]],x.vi[i]+y.vi[j]); }return c;} void build(int i,int l,int r){ if (l==r){paint(i,l);return;} int mid=l+r>>1; build(i<<1,l,mid);build(i<<1|1,mid+1,r); tr[i]=updata(tr[i<<1],tr[i<<1|1]);} use ask(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr) return tr[i]; int mid=l+r>>1;use x1,x2; bool f1,f2;f1=f2=false; if (ll<=mid){f1=true;x1=ask(i<<1,l,mid,ll,rr);} if (rr>mid){f2=true;x2=ask(i<<1|1,mid+1,r,ll,rr);} if (!f1) return x2; if (!f2) return x1; return updata(x1,x2);} void tch(int i,int l,int r,int x){ if (l==r){paint(i,l);return;} int mid=l+r>>1; if (x<=mid) tch(i<<1,l,mid,x); else tch(i<<1|1,mid+1,r,x); tr[i]=updata(tr[i<<1],tr[i<<1|1]);} int main(){ int n,m,i,j,x0,y0,x1,y1;LL w;scanf("%d%d",&n,&m); for (i=1;i<n;++i) scanf("%I64d",&ed[0][i]); for (i=1;i<n;++i) scanf("%I64d",&ed[1][i]); for (i=1;i<=n;++i) scanf("%I64d",&ed[2][i]); --n;build(1,1,n); for (i=1;i<=m;++i){ char ch=in(); if (ch=='Q'){ scanf("%d%d",&y0,&y1); if (y1<y0) swap(y0,y1); if (y0==y1) printf("%I64d ",ed[2][y0]); else{ use xx=ask(1,1,n,y0,y1-1); printf("%I64d ",xx.vi[4]); } }else{ scanf("%d%d%d%d%I64d",&x0,&y0,&x1,&y1,&w); if (x0==x1){ if (y0>y1) swap(y0,y1); ed[x0-1][y0]=w; tch(1,1,n,y0); }else{ ed[2][y0]=w; if (y0>1) tch(1,1,n,y0-1); if (y0<=n) tch(1,1,n,y0); } } } }
bzoj2752 高速公路
题目大意：n个点n-1条边，操作有：区间加；查询一段区间内任选两点a、b(a<b)，求从a～b路径和的期望。
思路：维护一坨东西的线段树（从更新的时候的表达式上入手就可以了）。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 100005 #define LL long long using namespace std; struct use{ LL ans,sum,del,lx,rx,len,lr,l,r; void init(){ans=sum=del=lx=rx=0LL;lr=l=r=len=1LL;} }tr[N*4]={0LL}; char in(){ char ch=getchar(); while(ch<'A'||ch>'Z') ch=getchar(); return ch;} LL gcd(LL x,LL y){return (!y ? x : gcd(y,x%y));} void paint(int i,LL x){ tr[i].del+=x;tr[i].sum+=tr[i].len*x; tr[i].lx=tr[i].lx+tr[i].l*x; tr[i].rx=tr[i].rx+tr[i].r*x; tr[i].ans=tr[i].ans+tr[i].lr*x;} void pushdown(int i,int l,int r){ if (tr[i].del){ int mid=l+r>>1; paint(i<<1,tr[i].del); paint(i<<1|1,tr[i].del); tr[i].del=0LL; }} use updata(use x,use y){ use c;c.init(); c.len=x.len+y.len; c.sum=x.sum+y.sum; c.ans=x.ans+y.ans+x.lx*y.len+y.rx*x.len; c.lx=x.lx+x.len*y.sum+y.lx; c.rx=x.rx+y.len*x.sum+y.rx; c.lr=x.lr+y.lr+x.len*y.r+y.len*x.l; c.l=x.l+y.l+y.len*x.len; c.r=x.r+y.r+x.len*y.len; return c;} void build(int i,int l,int r){ if (l==r){tr[i].init();return;} int mid=l+r>>1; build(i<<1,l,mid);build(i<<1|1,mid+1,r); tr[i]=updata(tr[i<<1],tr[i<<1|1]);} use ask(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr) return tr[i]; use x1,x2;bool f1,f2;f1=f2=false; int mid=l+r>>1;pushdown(i,l,r); if (ll<=mid){x1=ask(i<<1,l,mid,ll,rr);f1=true;} if (rr>mid){x2=ask(i<<1|1,mid+1,r,ll,rr);f2=true;} if (!f1) return x2; if (!f2) return x1; return updata(x1,x2);} void tch(int i,int l,int r,int ll,int rr,LL x){ if (ll<=l&&r<=rr){paint(i,x);return;} int mid=l+r>>1;pushdown(i,l,r); if (ll<=mid) tch(i<<1,l,mid,ll,rr,x); if (rr>mid) tch(i<<1|1,mid+1,r,ll,rr,x); tr[i]=updata(tr[i<<1],tr[i<<1|1]);} int main(){ int i,j,n,m,l,r;LL g,ci;char ch; scanf("%d%d",&n,&m);--n; build(1,1,n); for (i=1;i<=m;++i){ ch=in();scanf("%d%d",&l,&r); if (ch=='Q'){ use x=ask(1,1,n,l,r-1); g=gcd(x.ans,ci=(LL)(r-l+1)*(LL)(r-l)/2LL); printf("%I64d/%I64d ",x.ans/g,ci/g); }else{ scanf("%I64d",&ci); tch(1,1,n,l,r-1,ci); } } }
也可以从val[i](y-i+1)(i-x+1)的式子入手，只需要维护val[i],val[i]*i,val[i]*i*i就可以了。
bzoj1818 内部白点
题目大意：每一秒上下左右四个方向都有黑点的白色格点会变黑，一开始有n个黑点，求最终黑点的个数。如果变色过程永不停止，输出-1。
思路：所有变色的点会在第一秒变色并且不存在输出-1的情况。所以题目就变成了求所有线段（不含端点）的交点个数，+n就是答案了。求线段交点个数可以用线段树求解，对于竖着的线段先把两个端点处理出来，排序，然后扫横着的时候处理竖着的并且计算答案。
注意：有些语句其实并不等价，比如： add(1,1,cz,di[x].x,di[x].k);++x; 和 add(1,1,cz,di[x].x,di[x++].k);
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 200005 #define LL long long using namespace std; struct use{ int x,y,k; bool operator<(const use&a)const{return (x==a.x ? y<a.y : x<a.x);} }ai[N],di[N]; int bi[N],ci[N],tr[N<<2]={0}; int cmp(const use&a,const use&b){return (a.y==b.y ? a.x<b.x : a.y<b.y);} void add(int i,int l,int r,int x,int y){ if (l==r){tr[i]+=y;return;} int mid=l+r>>1; if (x<=mid) add(i<<1,l,mid,x,y); else add(i<<1|1,mid+1,r,x,y); tr[i]=tr[i<<1]+tr[i<<1|1];} int ask(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr) return tr[i]; int sum=0,mid=l+r>>1; if (ll<=mid) sum+=ask(i<<1,l,mid,ll,rr); if (rr>mid) sum+=ask(i<<1|1,mid+1,r,ll,rr); return sum;} void print(int i,int l,int r){ if (l==r){printf("%d ",tr[i]);return;} int mid=l+r>>1; print(i<<1,l,mid);print(i<<1|1,mid+1,r); } int main(){ int i,j,k,n,x,y,tt,cz;LL ans=0; scanf("%d",&n); for (i=1;i<=n;++i){ scanf("%d%d",&x,&y); ai[i]=(use){x,y};bi[i]=x; }sort(bi+1,bi+n+1); cz=unique(bi+1,bi+n+1)-bi-1; ci[tt=1]=bi[1]; for (i=2;i<=n;++i){ if (bi[i]-bi[i-1]>1) ci[++tt]=bi[i]-1; ci[++tt]=bi[i]; }sort(ci+1,ci+tt+1); cz=unique(ci+1,ci+tt+1)-ci-1; for (i=1;i<=n;++i) ai[i].x=upper_bound(ci+1,ci+cz+1,ai[i].x)-ci-1; sort(ai+1,ai+n+1); for (tt=0,i=1;i<=n;i=j+1){ j=i;while(j<n&&ai[j+1].x==ai[j].x) ++j; for (k=i+1;k<=j;++k) if (ai[k].y-ai[k-1].y>1){ di[++tt]=(use){ai[k-1].x,ai[k-1].y+1,1}; di[++tt]=(use){ai[k].x,ai[k].y,-1}; } }sort(di+1,di+tt+1,cmp); sort(ai+1,ai+n+1,cmp); for (x=1,i=1;i<=n;i=j+1){ j=i;while(j<n&&ai[j+1].y==ai[j].y) ++j; while(x<=tt&&di[x].y<=ai[j].y){ add(1,1,cz,di[x].x,di[x].k);++x; }for (k=i+1;k<=j;++k) if (ai[k].x-ai[k-1].x>1) ans+=(LL)ask(1,1,cz,ai[k-1].x+1,ai[k].x-1); }printf("%I64d ",ans+(LL)n); }
bzoj2811 guard（！！！）
题目大意：n个障碍后面有k个忍者（每个后面最多1个），m条信息表示a～b中有无忍者（0表示没有，1表示至少1个），求那些障碍后面一定有忍者。
思路：第一反应是差分约束，但是没法处理一定有的情况。先把一定没有的点去掉，剩下的可以重新编号1～up，互相包含的信息是需要删掉的，我们可以贪心算出1～i和i~mp（去掉信息后的信息总数）所需要的最少忍者数fi[i],gi[i]。判断每个贪心放忍者的位置x是否必须放，看x-1个位置能覆盖的区间l～r，如果fi[l-1]+1+gi[r+1]>k，就说明x-1不能放，必须放在x位置，找覆盖区间的时候可以二分。
注意：因为忍者是贪心放在右端点的，所以贪心放的时候mx不能在取max。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 100005 #define inf 2100000000 using namespace std; struct use{ int a,b; bool operator<(const use&x)const{return (a==x.a ? b<x.b : a<x.a);} }ai[N],qu[N]; int tr[N<<2]={0},del[N<<2]={0},bi[N]={0},fi[N]={0},gi[N]={0},pi[N]={0},qi[N]={0},cnt=0; void pushdown(int i){ tr[i<<1]=tr[i<<1|1]=del[i<<1]=del[i<<1|1]=1; del[i]=0;} void tch(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr){tr[i]=del[i]=1;return;} int mid=l+r>>1; if (del[i]) pushdown(i); if (ll<=mid) tch(i<<1,l,mid,ll,rr); if (rr>mid) tch(i<<1|1,mid+1,r,ll,rr);} void pre(int i,int l,int r){ if (l==r){ if (!tr[i]) bi[pi[l]=qi[l]=++cnt]=l; return; }int mid=l+r>>1; if (del[i]) pushdown(i); pre(i<<1,l,mid);pre(i<<1|1,mid+1,r);} int main(){ int n,m,i,k,a,b,c,az=0,mx,mn,l,r,mid; bool f=false; scanf("%d%d%d",&n,&k,&m); for (i=1;i<=m;++i){ scanf("%d%d%d",&a,&b,&c); if (!c) tch(1,1,n,a,b); else ai[++az]=(use){a,b}; }pre(1,1,n);qi[n+1]=inf; if (cnt==k){ for (i=1;i<=cnt;++i) printf("%d ",bi[i]); return 0; }for (i=1;i<=n;++i) if (!pi[i]) pi[i]=pi[i-1]; for (i=n;i;--i) if (!qi[i]) qi[i]=qi[i+1]; for (i=1;i<=az;++i){ ai[i].a=qi[ai[i].a]; ai[i].b=pi[ai[i].b]; }sort(ai+1,ai+az+1); for (cnt=0,i=1;i<=az;++i){ if (ai[i].a>ai[i].b) continue; while(cnt&&qu[cnt].a<=ai[i].a&&ai[i].b<=qu[cnt].b) --cnt; qu[++cnt]=ai[i]; }for (mx=0,i=1;i<=cnt;++i){ if (qu[i].a>mx){fi[i]=fi[i-1]+1;mx=qu[i].b;} else fi[i]=fi[i-1]; }for (mn=inf,i=cnt;i;--i){ if (qu[i].b<mn){gi[i]=gi[i+1]+1;mn=qu[i].a;} else gi[i]=gi[i+1]; }for (i=1;i<=cnt;++i){ if (fi[i]!=fi[i-1]+1) continue; if (qu[i].a==qu[i].b){ printf("%d ",bi[qu[i].a]); f=true; }else{ a=0;b=cnt+1;c=qu[i].b-1; l=1;r=i-1; while(l<=r){ mid=l+r>>1; if (qu[mid].b<c){ a=mid;l=mid+1; }else r=mid-1; }l=i+1;r=cnt; while(l<=r){ mid=l+r>>1; if (qu[mid].a>c){ b=mid;r=mid-1; }else l=mid+1; }if (fi[a]+1+gi[b]>k){ printf("%d ",bi[qu[i].b]); f=true; } } }if (!f) printf("-1 "); }
bzoj2333 棘手的操作
题目大意：一个数列n，一开始每个元素一个块，支持操作：1）连接u、v所在块；2）给某个数或者某个数所在块或者全部加v；3）查询某个数或者某个数所在块或者全部的最大值。
思路：类似merge，用线段树支持合并操作，维护最大值。再用一个线段树维护全局最大值。
正解好像是斜堆、可并堆什么的，然而并不会。。。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 300005 #define inf 2100000000 using namespace std; struct use{ int l,r,mx,del; void init(){l=r=del=mx=0;} }tr[N*20]; int rt[N]={0},fa[N],tot=0,ad=0,siz[N]={0},t[N<<2]; char ss[2]; int root(int x){return (fa[x]==x ? fa[x] : fa[x]=root(fa[x]));} void pushdown(int i){ if (tr[i].l){ tr[tr[i].l].del+=tr[i].del; tr[tr[i].l].mx+=tr[i].del; }if (tr[i].r){ tr[tr[i].r].del+=tr[i].del; tr[tr[i].r].mx+=tr[i].del; }tr[i].del=0; } void tch(int &i,int l,int r,int x,int y){ if (!i) tr[i=++tot].init(); if (l==r){tr[i].mx+=y;return;} int mid=(l+r)>>1; if (tr[i].del!=0) pushdown(i); if (x<=mid) tch(tr[i].l,l,mid,x,y); else tch(tr[i].r,mid+1,r,x,y); tr[i].mx=max(tr[tr[i].l].mx,tr[tr[i].r].mx); } void uni(int &x,int &y,int l,int r){ if (!y) return; if (!x){x=y;return;} int mid=(l+r)>>1; if (tr[x].del!=0) pushdown(x); if (tr[y].del!=0) pushdown(y); uni(tr[x].l,tr[y].l,l,mid); uni(tr[x].r,tr[y].r,mid+1,r); tr[x].mx=max(tr[tr[x].l].mx,tr[tr[x].r].mx); } int ask(int i,int l,int r,int x){ if (l==r) return tr[i].mx; int mid=(l+r)>>1; if (tr[i].del!=0) pushdown(i); if (x<=mid) return ask(tr[i].l,l,mid,x); else return ask(tr[i].r,mid+1,r,x); } void ttch(int i,int l,int r,int x,int y){ if (l==r){t[i]=y;return;} int mid=(l+r)>>1; if (x<=mid) ttch(i<<1,l,mid,x,y); else ttch(i<<1|1,mid+1,r,x,y); t[i]=max(t[i<<1],t[i<<1|1]); } int main(){ int n,q,i,u,v,r,x; scanf("%d",&n); tr[0].init();tr[0].mx=-inf; for (i=1;i<=n;++i){ scanf("%d",&x);fa[i]=i; tch(rt[i],1,n,i,x);siz[i]=1; ttch(1,1,n,i,x); }scanf("%d",&q); while(q--){ scanf("%s",ss); if (ss[0]=='U'){ scanf("%d%d",&u,&v); u=root(u);v=root(v); if (u==v) continue; if (siz[u]<siz[v]) swap(u,v); fa[v]=u;siz[u]+=siz[v]; uni(rt[u],rt[v],1,n); ttch(1,1,n,u,tr[rt[u]].mx); ttch(1,1,n,v,-inf); }if (ss[0]=='A'){ if (ss[1]=='1'){ scanf("%d%d",&u,&x);r=root(u); tch(rt[r],1,n,u,x); ttch(1,1,n,r,tr[rt[r]].mx); }if (ss[1]=='2'){ scanf("%d%d",&u,&x);u=root(u); tr[rt[u]].mx+=x;tr[rt[u]].del+=x; ttch(1,1,n,u,tr[rt[u]].mx); }if (ss[1]=='3'){scanf("%d",&x);ad+=x;} }if (ss[0]=='F'){ if (ss[1]=='1'){ scanf("%d",&u);r=root(u); printf("%d ",ask(rt[r],1,n,u)+ad); }if (ss[1]=='2'){ scanf("%d",&u);u=root(u); printf("%d ",tr[rt[u]].mx+ad); }if (ss[1]=='3') printf("%d ",t[1]+ad); } } }
bzoj1178 会议中心
题目大意：给定一些线段，求互不相交的最多能选多少条，并输出其中字典序最小的方案。
思路：可以先通过去除包含的情况，求出最多有多少条，然后贪心输出答案。从编号小的往大的枚举（所有线段），判断一条线段能不能取就是看这条线段所在的区间没有被覆盖，并且这条线段选了之后，两边（不是从1～l-1和r+1～n的区间，而是被已选的线段分开的区间中i所在的区间左右延伸的位置）能选的最大值+1是不是这个区间本身的最大值，如果是可以把这个区间分开，两边赋应该有的最大值。这些操作可以用线段树维护。求一个区间能取到的最大值可以用倍增的思想（！！！），通过去包含，可以预处理出每条线段贪心往后选的时候第2^j条线段是哪一个。
注意：算区间最多的时候要考虑很多边界情况。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 200005 #define M 400005 #define up 20 #define inf 2100000000 using namespace std; struct use{ int l,r,po; bool operator<(const use&x)const{return (l==x.l ? r>x.r : l<x.l);} }ai[N],que[N]; struct tree{int mn,mx,del;}tr[M<<2]; struct uu{int v,del;}tt[M<<2]; int fi[N][up]={0},asi[N],bi[M]={0},mi[N],cnt=0,bz; int cmp(const use&x,const use&y){return x.po<y.po;} void build(int i,int l,int r){ tr[i]=(tree){bz+1,0,0}; if (l==r) return; int mid=(l+r)>>1; build(i<<1,l,mid);build(i<<1|1,mid+1,r);} void push(int i,int l,int r){ int mid=(l+r)>>1; tr[i<<1]=(tree){l,mid,1}; tr[i<<1|1]=(tree){mid+1,r,1}; tr[i].del=0;} int amx(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr) return tr[i].mx; int mid=(l+r)>>1;int mx=0; if (tr[i].del) push(i,l,r); if (ll<=mid) mx=max(mx,amx(i<<1,l,mid,ll,rr)); if (rr>mid) mx=max(mx,amx(i<<1|1,mid+1,r,ll,rr)); return mx;} int amn(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr) return tr[i].mn; int mid=(l+r)>>1;int mn=bz+1; if (tr[i].del) push(i,l,r); if (ll<=mid) mn=min(mn,amn(i<<1,l,mid,ll,rr)); if (rr>mid) mn=min(mn,amn(i<<1|1,mid+1,r,ll,rr)); return mn;} void change(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr){tr[i]=(tree){l,r,1};return;} int mid=(l+r)>>1; if (tr[i].del) push(i,l,r); if (ll<=mid) change(i<<1,l,mid,ll,rr); if (rr>mid) change(i<<1|1,mid+1,r,ll,rr); tr[i].mn=min(tr[i<<1].mn,tr[i<<1|1].mn); tr[i].mx=max(tr[i<<1].mx,tr[i<<1|1].mx); } void pushdown(int i){ tt[i<<1]=tt[i<<1|1]=(uu){tt[i].del,tt[i].del}; tt[i].del=-1;} int ast(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr) return tt[i].v; int mid=(l+r)>>1;int mn=inf; if (tt[i].del>=0) pushdown(i); if (ll<=mid) mn=min(mn,ast(i<<1,l,mid,ll,rr)); if (rr>mid) mn=min(mn,ast(i<<1|1,mid+1,r,ll,rr)); return mn;} void tch(int i,int l,int r,int ll,int rr,int x){ if (ll<=l&&r<=rr){tt[i]=(uu){x,x};return;} int mid=(l+r)>>1; if (tt[i].del>=0) pushdown(i); if (ll<=mid) tch(i<<1,l,mid,ll,rr,x); if (rr>mid) tch(i<<1|1,mid+1,r,ll,rr,x); tt[i].v=min(tt[i<<1].v,tt[i<<1|1].v);} int calc(int ll,int rr){ if (ll>rr) return 0; int i,ans,l,r,mid; l=1;r=cnt; while(l!=r){ mid=(l+r)>>1; if (que[mid].l>=ll) r=mid; else l=mid+1; }if (que[l].r>rr||que[l].l<ll) return 0; for (ans=1,i=up-1;i>=0;--i) if (que[fi[l][i]].r<=rr){ ans+=mi[i];l=fi[l][i]; } return ans;} int main(){ int n,i,j,ans=0,mx,l,r,mid,l1,r1,l2,r2,c1,c2; scanf("%d",&n); for (mi[0]=i=1;i<up;++i) mi[i]=mi[i-1]<<1; for (i=1;i<=n;++i){ scanf("%d%d",&ai[i].l,&ai[i].r); ai[i].po=i;bi[++bi[0]]=ai[i].l; bi[++bi[0]]=ai[i].r; }sort(bi+1,bi+bi[0]+1); bz=unique(bi+1,bi+bi[0]+1)-bi-1; for (i=1;i<=n;++i){ ai[i].l=upper_bound(bi+1,bi+bz+1,ai[i].l)-bi-1; ai[i].r=upper_bound(bi+1,bi+bz+1,ai[i].r)-bi-1; }sort(ai+1,ai+n+1); for (i=1;i<=n;++i){ while(cnt&&ai[i].l>=que[cnt].l&&ai[i].r<=que[cnt].r) --cnt; que[++cnt]=ai[i]; }que[cnt+1].l=que[cnt+1].r=inf; for (j=0;j<up;++j) fi[cnt][j]=fi[cnt+1][j]=cnt+1; for (mx=cnt,i=cnt-1;i;--i){ while(que[mx].l>que[i].r) --mx; fi[i][0]=mx+1; for (j=1;j<up;++j) fi[i][j]=fi[fi[i][j-1]][j-1]; }for (mx=0,i=1;i<=cnt;++i) if (que[i].l>mx){mx=que[i].r;++ans;} printf("%d ",ans); sort(ai+1,ai+n+1,cmp);build(1,1,bz); for (i=(M<<2)-1;i;--i) tt[i]=(uu){inf,-1}; tt[1].del=tt[1].v=ans; for (i=1;i<=n;++i){ mx=ast(1,1,bz,ai[i].l,ai[i].r); if (mx==0) continue; r1=ai[i].l-1; if (r1>=1) l1=amx(1,1,bz,1,r1)+1; else l1=inf; c1=calc(l1,r1); l2=ai[i].r+1; if (l2<=bz) r2=amn(1,1,bz,l2,bz)-1; else r2=0; c2=calc(l2,r2); if (c1+c2+1==mx){ tch(1,1,bz,ai[i].l,ai[i].r,0); change(1,1,bz,ai[i].l,ai[i].r); if (l1<=r1) tch(1,1,bz,l1,r1,c1); if (l2<=r2) tch(1,1,bz,l2,r2,c2); printf("%d ",i); } }printf(" "); }
bzoj1558 等差数列
题目大意：维护一个数列，支持：1）给[s,t]中的数加上一个首项是a，公差是b的等差数列；2）查询[s,t]中最少分成多少连续的段，使得每个段都是一个等差数列。
思路：先差分，线段树维护这个区间左边差连续不同的个数、右边差连续不同的个数、除左右不连续的部分其他的答案（！！！）。然后线段树维护就可以了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 100005 using namespace std; struct use{ int lv,rv,del,ans,la,ra,len; }tr[N<<2]; int ai[N]={0}; char in(){ char ch=getchar(); while(ch<'A'||ch>'Z') ch=getchar(); return ch;} use updata(use x,use y){ use c;c.del=0;c.len=x.len+y.len; c.lv=x.lv;c.rv=y.rv; c.la=x.la;c.ra=y.ra; c.ans=x.ans+y.ans; if (!x.ans&&!y.ans){ if (x.rv==y.lv){ c.ans=1;c.la=max(0,c.la-1); c.ra=max(0,c.ra-1); }else c.la=c.ra=c.len; return c; }if (!x.ans){ if (x.rv==y.lv){ c.ans+=(y.la-1)/2+(y.la ? 1 : 0); c.la=max(0,c.la-1); }else c.la+=y.la; return c; }if (!y.ans){ if (x.rv==y.lv){ c.ans+=(x.ra-1)/2+(x.ra ? 1 : 0); c.ra=max(0,c.ra-1); }else c.ra+=x.ra; return c; }if (!x.ra&&!y.la){ if (x.rv==y.lv) --c.ans; return c; }if (!x.ra){ if (x.rv==y.lv) c.ans+=(y.la-1)/2; else c.ans+=y.la/2; return c; }if (!y.la){ if (x.rv==y.lv) c.ans+=(x.ra-1)/2; else c.ans+=x.ra/2; return c; }if (x.rv==y.lv) c.ans+=(x.ra-1)/2+(y.la-1)/2+1; else c.ans+=(x.ra+y.la)/2; return c;} void build(int i,int l,int r){ if (l==r){ int x=(ai[l]-ai[l-1]); tr[i]=(use){x,x,0,0,1,1,1}; return; }int mid=(l+r)>>1; build(i<<1,l,mid);build(i<<1|1,mid+1,r); tr[i]=updata(tr[i<<1],tr[i<<1|1]);} void pushdown(int i){ int x=tr[i].del; tr[i<<1].del+=x;tr[i<<1].lv+=x;tr[i<<1].rv+=x; tr[i<<1|1].del+=x;tr[i<<1|1].lv+=x;tr[i<<1|1].rv+=x; tr[i].del=0;} void chv(int i,int l,int r,int x,int y){ if (l==r){tr[i].lv+=y;tr[i].rv+=y;return;} int mid=(l+r)>>1; if (tr[i].del!=0) pushdown(i); if (x<=mid) chv(i<<1,l,mid,x,y); else chv(i<<1|1,mid+1,r,x,y); tr[i]=updata(tr[i<<1],tr[i<<1|1]);} void tch(int i,int l,int r,int ll,int rr,int x){ if (ll<=l&&r<=rr){ tr[i].lv+=x;tr[i].rv+=x; tr[i].del+=x;return; }int mid=(l+r)>>1; if (tr[i].del!=0) pushdown(i); if (ll<=mid) tch(i<<1,l,mid,ll,rr,x); if (rr>mid) tch(i<<1|1,mid+1,r,ll,rr,x); tr[i]=updata(tr[i<<1],tr[i<<1|1]);} use ask(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr) return tr[i]; int mid=(l+r)>>1; if (tr[i].del!=0) pushdown(i); use u1,u2;bool f1,f2;f1=f2=false; if (ll<=mid){f1=true;u1=ask(i<<1,l,mid,ll,rr);} if (rr>mid){f2=true;u2=ask(i<<1|1,mid+1,r,ll,rr);} if (!f2) return u1; if (!f1) return u2; return updata(u1,u2);} int main(){ int n,m,i,j,a,b,s,t;use uu; char ch;scanf("%d",&n); for (i=1;i<=n;++i) scanf("%d",&ai[i]); build(1,1,n);scanf("%d",&m); for (i=1;i<=m;++i){ ch=in(); if (ch=='A'){ scanf("%d%d%d%d",&s,&t,&a,&b); chv(1,1,n,s,a); if (t<n) chv(1,1,n,t+1,-a-(t-s)*b); if (s<t) tch(1,1,n,s+1,t,b); }else{ scanf("%d%d",&s,&t);uu=ask(1,1,n,s,t); printf("%d ",uu.ans+(!uu.ans ? (uu.la+1)/2 : uu.la/2+(uu.ra+1)/2)); } } }
bzoj4447 小凸解密码
题目大意：给定一个数列ai和符号ci，bi的生成方式是从一个位置开始，b0=a0，bi=（ai-1 ci ai）%10，将bi成环，一段都是0的区间到b0的距离是离b0最近的距离。操作：1）修改某个位置的ai和ci；2）问这个环上离b0最远的0区间的距离。
思路：环拆成两倍的序列，因为每个位置的值都是固定的，用线段树维护一个区间内最左边的0区间的右端点和最右边的0区间的左端点，查询的时候找中间的三个个区间取最大值就可以了。
注意：1）线段树updata的时候，对于左右的右左端点，还要考虑到左或右区间没有0区间的情况；
2）修改操作的时候，bi的值要用自己的下标算，不然可能出现计算1和1+n的时候用到0的数。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 200005 #define p 10 using namespace std; struct use{int ls,rs,lm,rm,l,r,len;}tr[N<<2]={0}; int ai[N]={0},bi[N]={0},cf[N]={0}; int in(){ char ch=getchar(); while(ch!='+'&&ch!='*') ch=getchar(); return ch=='*';} int calc(int x){return (cf[x] ? ai[x-1]*ai[x] : ai[x-1]+ai[x])%p;} use updata(use a,use b){ use c;c.l=a.l;c.r=b.r; c.len=a.len+b.len; c.ls=a.ls;c.rs=b.rs; if (c.ls==a.len) c.ls+=b.ls; if (c.rs==b.len) c.rs+=a.rs; c.lm=a.lm;c.rm=b.rm; if ((a.lm==a.r&&b.ls)||!a.lm) c.lm=b.lm; if ((b.rm==b.l&&a.rs)||!b.rm) c.rm=a.rm; return c;} void build(int i,int l,int r){ if (l==r){ tr[i].len=r-l+1;tr[i].l=l;tr[i].r=r; if (!bi[l]){ tr[i].ls=tr[i].rs=1; tr[i].lm=tr[i].rm=l; }return; }int mid=(l+r)>>1; build(i<<1,l,mid);build(i<<1|1,mid+1,r); tr[i]=updata(tr[i<<1],tr[i<<1|1]);} void tch(int i,int l,int r,int x){ if (l==r){ if (!bi[l]){ tr[i].ls=tr[i].rs=1; tr[i].lm=tr[i].rm=l; }else tr[i].ls=tr[i].rs=tr[i].lm=tr[i].rm=0; return; }int mid=(l+r)>>1; if (x<=mid) tch(i<<1,l,mid,x); else tch(i<<1|1,mid+1,r,x); tr[i]=updata(tr[i<<1],tr[i<<1|1]);} use ask(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr) return tr[i]; int mid=(l+r)>>1;use a,b; bool f1,f2;f1=f2=false; if (ll<=mid){f1=true;a=ask(i<<1,l,mid,ll,rr);} if (rr>mid){f2=true;b=ask(i<<1|1,mid+1,r,ll,rr);} if (f1&&f2) return updata(a,b); if (f1) return a; else return b;} int main(){ int n,m,i,j,op,x,y,z,mid,ans;use a,b,c,lx,rx; scanf("%d%d",&n,&m); for (i=1;i<=n;++i){ scanf("%d",&ai[i]); ai[i+n]=ai[i]; cf[i]=cf[i+n]=in(); }for (i=2;i<=(n<<1);++i) bi[i]=calc(i); build(1,1,n<<1); for (i=1;i<=m;++i){ scanf("%d",&op); if (op==1){ scanf("%d%d",&x,&y);z=in();++x; cf[x]=cf[x+n]=z;ai[x]=ai[x+n]=y; bi[x]=calc(x);tch(1,1,n<<1,x); bi[x+n]=calc(x+n);tch(1,1,n<<1,x+n); bi[x+1]=calc(x+1);tch(1,1,n<<1,x+1); if (x+1<=n){bi[x+n+1]=calc(x+n+1);tch(1,1,n<<1,x+n+1);} }else{ scanf("%d",&x);ans=-1; ++x;mid=x+(n>>1); if (ai[x]){ lx=(use){0,0,0,0,x,x,1}; rx=(use){0,0,0,0,x+n,x+n,1}; }else{ lx=(use){1,1,x,x,x,x,1}; rx=(use){1,1,x+n,x+n,x+n,x+n,1}; }a=ask(1,1,n<<1,x+1,mid); a=updata(lx,a); b=ask(1,1,n<<1,mid+1,x+n-1); b=updata(b,rx); if (a.rs&&b.ls){ ans=max(ans,min(a.rm-x,x+n-b.lm)); if (a.rm-x>=2){ a=ask(1,1,n<<1,x+1,a.rm-1); a=updata(lx,a); if (a.rm) ans=max(ans,a.rm-x); }if (x+n-b.lm>=2){ b=ask(1,1,n<<1,b.lm+1,x+n-1); b=updata(b,rx); if (b.lm) ans=max(ans,x+n-b.lm); } }else{ if (a.rm) ans=max(ans,a.rm-x); if (b.lm) ans=max(ans,x+n-b.lm); }printf("%d ",ans); } } }
bzoj3938 Robot
题目大意：有n个机器人，m组操作：（1）某个机器人从t之后每秒移动x；（2）问t秒是距原点最远的机器人的距离。
思路：对时间建维护最大最小值的两个线段树，每个（1）操作可以看作在这一次和下一次操作时间上加一条线段，（2）是单点查询最大值和最小值绝对值中的较大值。插入线段用类似bzoj1568、bzoj4515的log^2n的做法。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 600005 #define LL long long using namespace std; struct Q{int k,ki,s,t;LL x;}ask[N]; struct line{LL k,b;}; struct T{LL mx;line x;bool ex;}tr[N<<2]; struct TT{LL mn;line x;bool ex;}tm[N<<2]; int tt=0,tz=0,la[N]; LL ti[N],xi[N]; char ss[10]; int in(){ char ch=getchar();int x=0,f=1; while((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar(); }return x*f;} void build(int i,int l,int r){ tr[i]=(T){0LL,(line){0LL,0LL},false}; tm[i]=(TT){0LL,(line){0LL,0LL},false}; if (l==r) return; int mid=(l+r)>>1; build(i<<1,l,mid);build(i<<1|1,mid+1,r);} LL getf(int x,line y){return ti[x]*y.k+y.b;} void ins(int i,int l,int r,int ll,int rr,line x){ if (ll<=l&&r<=rr){ tr[i].mx=max(tr[i].mx,max(getf(l,x),getf(r,x))); if (!tr[i].ex){tr[i].x=x;tr[i].ex=true;return;} if (l==r){ if (getf(l,x)>getf(l,tr[i].x)) tr[i].x=x; return; }int a,b,c,mid=(l+r)>>1; a=(getf(l,x)>getf(l,tr[i].x)); b=(getf(mid,x)>getf(mid,tr[i].x)); c=(getf(r,x)>getf(r,tr[i].x)); if (a&&c){tr[i].x=x;return;} if ((!a)&&(!c)) return; if (b){swap(x,tr[i].x);a^=1;c^=1;} if (a) ins(i<<1,l,mid,ll,rr,x); if (c) ins(i<<1|1,mid+1,r,ll,rr,x); return; }int mid=(l+r)>>1; if (ll<=mid) ins(i<<1,l,mid,ll,rr,x); if (rr>mid) ins(i<<1|1,mid+1,r,ll,rr,x); tr[i].mx=max(tr[i].mx,max(tr[i<<1].mx,tr[i<<1|1].mx)); } void tin(int i,int l,int r,int ll,int rr,line x){ if (ll<=l&&r<=rr){ tm[i].mn=min(tm[i].mn,min(getf(l,x),getf(r,x))); if (!tm[i].ex){tm[i].x=x;tm[i].ex=true;return;} if (l==r){ if (getf(l,x)<getf(l,tm[i].x)) tm[i].x=x; return; }int a,b,c,mid=(l+r)>>1; a=(getf(l,x)<getf(l,tm[i].x)); b=(getf(mid,x)<getf(mid,tm[i].x)); c=(getf(r,x)<getf(r,tm[i].x)); if (a&&c){tm[i].x=x;return;} if ((!a)&&(!c)) return; if (b){swap(x,tm[i].x);a^=1;c^=1;} if (a) tin(i<<1,l,mid,ll,rr,x); if (c) tin(i<<1|1,mid+1,r,ll,rr,x); return; }int mid=(l+r)>>1; if (ll<=mid) tin(i<<1,l,mid,ll,rr,x); if (rr>mid) tin(i<<1|1,mid+1,r,ll,rr,x); tm[i].mn=min(tm[i].mn,min(tm[i<<1].mn,tm[i<<1|1].mn)); } LL atr(int i,int l,int r,int x){ if (l==r) return tr[i].mx; int mid=(l+r)>>1;LL mx=0LL; if (tr[i].ex) mx=max(mx,getf(x,tr[i].x)); if (x<=mid) mx=max(mx,atr(i<<1,l,mid,x)); else mx=max(mx,atr(i<<1|1,mid+1,r,x)); return mx;} LL atm(int i,int l,int r,int x){ if (l==r) return tm[i].mn; int mid=(l+r)>>1;LL mn=0; if (tm[i].ex) mn=min(mn,getf(x,tm[i].x)); if (x<=mid) mn=min(mn,atm(i<<1,l,mid,x)); else mn=min(mn,atm(i<<1|1,mid+1,r,x)); return mn;} int main(){ int n,m,i,t; n=in();m=in(); for (i=1;i<=n;++i) xi[i]=(LL)in(); for (i=1;i<=m;++i){ t=in();scanf("%s",ss); ti[++tz]=(LL)t; if (ss[0]=='c') ask[i]=(Q){0,in(),t,0,(LL)in()}; else ask[i]=(Q){1,0,t,0,0LL}; }sort(ti+1,ti+tz+1); tz=unique(ti+1,ti+tz+1)-ti-1; for (i=1;i<=n;++i) la[i]=tz; for (i=m;i;--i){ ask[i].s=upper_bound(ti+1,ti+tz+1,(LL)ask[i].s)-ti-1; if (!ask[i].k){ ask[i].t=la[ask[i].ki]; la[ask[i].ki]=ask[i].s; } }for (i=1;i<=n;++i){ ins(1,1,tz,1,la[i],(line){0LL,xi[i]}); tin(1,1,tz,1,la[i],(line){0LL,xi[i]}); }for (i=1;i<=m;++i){ if (!ask[i].k){ if (ask[i].s<ask[i].t){ ins(1,1,tz,ask[i].s+1,ask[i].t,(line){ask[i].x,xi[ask[i].ki]-ti[ask[i].s]*ask[i].x}); tin(1,1,tz,ask[i].s+1,ask[i].t,(line){ask[i].x,xi[ask[i].ki]-ti[ask[i].s]*ask[i].x}); }xi[ask[i].ki]+=ask[i].x*(ti[ask[i].t]-ti[ask[i].s]); }else printf("%I64d ",max(atr(1,1,tz,ask[i].s),-atm(1,1,tz,ask[i].s))); } }
bzoj4085 quality
题目大意：给定一个序列a[i]和函数f[i](f[1]=1,f[2]=2,f[i]=f[i-1]+a*f[i-2]+b(i>=3))。支持三种操作：（1）查询sigma(i=l+1~r-1)f[a[i-1]+1]*f[a[i+1]-1]；（2）给a[l~r]都+1；（3）给a[l~r]都-1。
思路：如果a！=0：令x表示a[i-1]+1,y表示a[i+1]-1,线段树维护x*y,(x-1)*(y-1),(x+1)*(y+1),(x-1)*y,x*(y-1),(x+1)*y,x*(y+1),x,y,x-1,y-1,x+1,y+1。只有第一次算的时候要矩乘（这里用3*3的会比较慢，所以可以优化成2*2的，令k=b/a，f[i]+k=f[i-1]+k+a*(f[i-2]+k)，在第一次处理的时候，把ai排序，从小到大算，就可以节省很多时间（！）)。对于+1/-1相应的更新，放标记的时候可以暴力放（数据比较弱）。查询答案就是x*y-k*(x+y-2*k*(r-l-1))-(r-l-1)*k*k。
如果a=0：相当于一个等差数列（除第一项，数据比较水，没有用到第一项的地方），更新的时候+b/-b就可以了（注意对区间维护x这类的时候，+/- b*len）。
修改的时候区间l+1~r-1是x和y都+/-1，四个边界l-1、l、r、r+1只需要对x/y +/-1。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long #define p 1000000007 #define N 300005 using namespace std; struct use{ LL x1y1,x0y0,x1y0,x0y1,x2y2,x1y2,x2y1,x0,x1,x2,y0,y1,y2,len; int del; }tr[N<<2]; LL kk,a,b,ia,ai[N],x1y1,s1,fi[2][N][3],cf[N<<1][3],ci[N<<1],cz=0; int n; char ss[10]; int in(){ char ch=getchar();int x=0; while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar(); }return x;} struct mat{ LL nm[2][2]; void init(){ nm[0][0]=nm[1][1]=1LL; nm[0][1]=nm[1][0]=0LL;} mat operator*(const mat&x)const{ mat c;int i,j,k; for (i=0;i<2;++i) for (j=0;j<2;++j){ c.nm[i][j]=0LL; for (k=0;k<2;++k) c.nm[i][j]=(c.nm[i][j]+nm[i][k]*x.nm[k][j]%p)%p; }return c;} }ji,zh; LL mi(LL x,LL y){ LL a=1LL; for (;y;y>>=1LL){ if (y&1LL) a=a*x%p; x=x*x%p; }return a;} mat mm(mat x,LL y){ mat c;c.init(); for (;y;y>>=1LL){ if (y&1LL) c=c*x; x=x*x; }return c;} void getf(LL x,LL la,LL &x1,LL &x2){ if (a){ ji=ji*mm(zh,x-la); x1=ji.nm[0][0];x2=ji.nm[0][1]; }else{ x1=(2LL+b*(x-3LL)%p)%p; x2=(x1+b)%p; }} void updata(int i){ int l=i<<1;int r=i<<1|1; tr[i].len=tr[l].len+tr[r].len; tr[i].x1y1=(tr[l].x1y1+tr[r].x1y1)%p; tr[i].x0y0=(tr[l].x0y0+tr[r].x0y0)%p; tr[i].x1y0=(tr[l].x1y0+tr[r].x1y0)%p; tr[i].x0y1=(tr[l].x0y1+tr[r].x0y1)%p; tr[i].x2y2=(tr[l].x2y2+tr[r].x2y2)%p; tr[i].x1y2=(tr[l].x1y2+tr[r].x1y2)%p; tr[i].x2y1=(tr[l].x2y1+tr[r].x2y1)%p; tr[i].x0=(tr[l].x0+tr[r].x0)%p; tr[i].x1=(tr[l].x1+tr[r].x1)%p; tr[i].x2=(tr[l].x2+tr[r].x2)%p; tr[i].y0=(tr[l].y0+tr[r].y0)%p; tr[i].y1=(tr[l].y1+tr[r].y1)%p; tr[i].y2=(tr[l].y2+tr[r].y2)%p;} void paint(int i,int l,int k1,int k2){ LL x0,x1,x2,y0,y1,y2; if (k1==-1&&!k2){ x0=fi[1][l-1][0];x1=fi[1][l-1][1];x2=fi[1][l-1][2]; y0=fi[0][l+1][0];y1=fi[0][l+1][1];y2=fi[0][l+1][2]; }if (k1==0){ y0=tr[i].y0;y1=tr[i].y1;y2=tr[i].y2; if (k2==1){ x0=tr[i].x1;x1=tr[i].x2; if (a) x2=(x0*a%p+x1)%p; else x2=(x1+b)%p; }else{ x1=tr[i].x0;x2=tr[i].x1; if (a) x0=(ia*(x2-x1)%p+p)%p; else x0=(x1-b+p)%p; } }if (k1==1){ x0=tr[i].x0;x1=tr[i].x1;x2=tr[i].x2; if (k2==1){ y0=tr[i].y1;y1=tr[i].y2; if (a) y2=(y0*a%p+y1)%p; else y2=(y1+b)%p; }else{ y1=tr[i].y0;y2=tr[i].y1; if (a) y0=(ia*(y2-y1)%p+p)%p; else y0=(y1-b+p)%p; } }tr[i].x0=x0;tr[i].x1=x1;tr[i].x2=x2; tr[i].y0=y0;tr[i].y1=y1;tr[i].y2=y2; tr[i].x1y1=x1*y1%p;tr[i].x0y0=x0*y0%p; tr[i].x2y2=x2*y2%p;tr[i].x1y0=x1*y0%p; tr[i].x0y1=x0*y1%p;tr[i].x1y2=x1*y2%p; tr[i].x2y1=x2*y1%p;tr[i].len=1LL;} void build(int i,int l,int r){ if (l==r){tr[i].del=0;paint(i,l,-1,0);return;} int mid=(l+r)>>1; build(i<<1,l,mid);build(i<<1|1,mid+1,r); updata(i);} void add(use &x){ use c;c.del=x.del;c.len=x.len; c.x0y0=x.x1y1;c.x1y1=x.x2y2; c.x1y0=x.x2y1;c.x0y1=x.x1y2; c.x0=x.x1;c.x1=x.x2; c.y0=x.y1;c.y1=x.y2; if (a){ c.x2y2=(c.x1y1+a*(c.x1y0+c.x0y1)%p+a*a%p*c.x0y0%p)%p; c.x1y2=(c.x1y1+a*c.x1y0%p)%p; c.x2y1=(c.x1y1+a*c.x0y1%p)%p; c.x2=(c.x1+a*c.x0%p)%p; c.y2=(c.y1+a*c.y0%p)%p; }else{ c.x2y2=(c.x1y1+b*(c.x1+c.y1)%p+b*b%p*c.len%p)%p; c.x1y2=(c.x1y1+b*c.x1%p)%p; c.x2y1=(c.x1y1+b*c.y1%p)%p; c.x2=(c.x1+b*c.len%p)%p; c.y2=(c.y1+b*c.len%p)%p; }x=c;} void minu(use &x){ use c;c.del=x.del;c.len=x.len; c.x1y1=x.x0y0;c.x2y2=x.x1y1; c.x2y1=x.x1y0;c.x1y2=x.x0y1; c.x1=x.x0;c.x2=x.x1; c.y1=x.y0;c.y2=x.y1; if (a){ c.x0y0=ia*ia%p*((c.x2y2+c.x1y1-c.x2y1-c.x1y2)%p+p)%p; c.x1y0=(ia*(c.x1y2-c.x1y1)%p+p)%p; c.x0y1=(ia*(c.x2y1-c.x1y1)%p+p)%p; c.x0=(ia*(c.x2-c.x1)%p+p)%p; c.y0=(ia*(c.y2-c.y1)%p+p)%p; }else{ c.x0y0=((c.x1y1-b*(c.x1+c.y1)%p+b*b%p*c.len%p)%p+p)%p; c.x1y0=((c.x1y1-b*c.x1%p)%p+p)%p; c.x0y1=((c.x1y1-b*c.y1%p)%p+p)%p; c.x0=((c.x1-b*c.len%p)%p+p)%p; c.y0=((c.y1-b*c.len%p)%p+p)%p; }x=c;} void pushdown(int i){ int l=i<<1;int r=i<<1|1; if (tr[i].del>0){ for (;tr[i].del>0;--tr[i].del){ ++tr[l].del;++tr[r].del; add(tr[l]);add(tr[r]); } }else{ for (;tr[i].del<0;++tr[i].del){ --tr[l].del;--tr[r].del; minu(tr[l]);minu(tr[r]); } }} void tch(int i,int l,int r,int ll,int rr,int x){ if (ll<=l&&r<=rr){ tr[i].del+=x; if (x==1) add(tr[i]); else minu(tr[i]); return; }int mid=(l+r)>>1; if (tr[i].del!=0) pushdown(i); if (ll<=mid) tch(i<<1,l,mid,ll,rr,x); if (rr>mid) tch(i<<1|1,mid+1,r,ll,rr,x); updata(i);} void ins(int i,int l,int r,int x,int y,int z){ if (l==r){paint(i,l,y,z);return;} int mid=(l+r)>>1; if (tr[i].del!=0) pushdown(i); if (x<=mid) ins(i<<1,l,mid,x,y,z); else ins(i<<1|1,mid+1,r,x,y,z); updata(i);} void ask(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr){ x1y1=(x1y1+tr[i].x1y1)%p; s1=(s1+tr[i].x1+tr[i].y1)%p; return; }int mid=(l+r)>>1; if (tr[i].del!=0) pushdown(i); if (ll<=mid) ask(i<<1,l,mid,ll,rr); if (rr>mid) ask(i<<1|1,mid+1,r,ll,rr);} int main(){ int q,i,l,r; n=in();q=in();a=(LL)in();b=(LL)in(); for (i=1;i<=n;++i){ ai[i]=(LL)in(); ci[++cz]=ai[i]-1LL; ci[++cz]=ai[i]+1LL; }ia=mi(a,p-2LL);kk=b*ia%p; ji.nm[0][0]=(1LL+kk)%p;ji.nm[0][1]=(2LL+kk)%p; ji.nm[1][0]=ji.nm[1][1]=0LL; zh.nm[0][0]=0LL;zh.nm[0][1]=a; zh.nm[1][0]=zh.nm[1][1]=1LL; sort(ci+1,ci+cz+1);cz=unique(ci+1,ci+cz+1)-ci-1; for (ci[0]=2LL,i=1;i<=cz;++i){ getf(ci[i],ci[i-1],cf[i][0],cf[i][1]); if (a) cf[i][2]=(cf[i][0]*a%p+cf[i][1])%p; else cf[i][2]=(cf[i][1]+b)%p; }for (i=1;i<=n;++i){ l=upper_bound(ci+1,ci+cz+1,ai[i]-1LL)-ci-1; for (r=0;r<3;++r) fi[0][i][r]=cf[l][r]; l=upper_bound(ci+1,ci+cz+1,ai[i]+1LL)-ci-1; for (r=0;r<3;++r) fi[1][i][r]=cf[l][r]; }build(1,2,n-1); for (i=1;i<=q;++i){ scanf("%s",ss); l=in();r=in(); if (ss[0]=='p'){ if (r-l>1) tch(1,2,n-1,l+1,r-1,1); if (l>1){ if (l<r) ins(1,2,n-1,l,1,1); if (l>2) ins(1,2,n-1,l-1,1,1); }if (r<n){ if (l<r) ins(1,2,n-1,r,0,1); if (r<n-1) ins(1,2,n-1,r+1,0,1); } }if (ss[0]=='m'){ if (r-l>1) tch(1,2,n-1,l+1,r-1,-1); if (l>1){ if (l<r) ins(1,2,n-1,l,1,-1); if (l>2) ins(1,2,n-1,l-1,1,-1); }if (r<n){ if (l<r) ins(1,2,n-1,r,0,-1); if (r<n-1) ins(1,2,n-1,r+1,0,-1); } }if (ss[0]=='q'){ if (r-l>1){ x1y1=s1=0LL; ask(1,2,n-1,l+1,r-1); printf("%I64d ",((x1y1-kk*(s1-kk*2LL*(LL)(r-l-1LL)%p)%p- kk*kk%p*(LL)(r-l-1LL)%p)%p+p)%p); }else printf("0 "); } } }
题目大意：给出数列ai，支持：（1）单点修改；（2）对一段区间排序后看是否是一个公差为k的等差数列。（强制在线）
思路：可以hash区间ai和ai^2的和，然后根据区间最小值算一下是否是线段树维护的值。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 300005 #define LL long long #define UL unsigned long long #define p 1000000007LL #define p2 325117697LL using namespace std; struct use{UL rm1;LL rm2,rm3,sm,mn,mx;}tr[N<<2]; LL ai[N]; UL usqr(LL x){return (UL)x*(UL)x;} LL sqr(LL x){return x*x%p;} LL sqr2(LL x){return x*x%p2;} int in(){ char ch=getchar();int x=0; while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar(); }return x;} use updata(use x,use y){ use c; c.rm1=x.rm1+y.rm1; c.rm2=(x.rm2+y.rm2)%p; c.rm3=(x.rm3+y.rm3)%p2; c.sm=x.sm+y.sm; c.mn=min(x.mn,y.mn); c.mx=max(x.mx,y.mx); return c;} void build(int i,int l,int r){ if (l==r){ tr[i]=(use){usqr(ai[l]),sqr(ai[l]),sqr2(ai[l]),ai[l],ai[l],ai[l]}; return; }int mid=(l+r)>>1; build(i<<1,l,mid);build(i<<1|1,mid+1,r); tr[i]=updata(tr[i<<1],tr[i<<1|1]);} void tch(int i,int l,int r,int x,LL y){ if (l==r){ tr[i]=(use){usqr(y),sqr(y),sqr2(y),y,y,y}; return; }int mid=(l+r)>>1; if (x<=mid) tch(i<<1,l,mid,x,y); else tch(i<<1|1,mid+1,r,x,y); tr[i]=updata(tr[i<<1],tr[i<<1|1]);} use ask(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr) return tr[i]; int mid=(l+r)>>1;use c1,c2; bool f1,f2;f1=f2=false; if (ll<=mid){f1=true;c1=ask(i<<1,l,mid,ll,rr);} if (rr>mid){f2=true;c2=ask(i<<1|1,mid+1,r,ll,rr);} if (!f1) return c2; if (!f2) return c1; return updata(c1,c2);} LL getn(LL x){return x*(x+1LL)*(2LL*x+1LL)/6LL;} int main(){ int i,j,n,m,op,x,y,cnt=0; LL k,sm,rm2,rm3,a1,ni;use ci;UL rm1; n=in();m=in(); for (i=1;i<=n;++i) ai[i]=(LL)in(); build(1,1,n); while(m--){ op=in();x=in()^cnt;y=in()^cnt; if (op==1) tch(1,1,n,x,(LL)y); else{ k=(LL)(in()^cnt); if (x>y) swap(x,y); ci=ask(1,1,n,x,y); a1=ci.mn;ni=(LL)(y-x+1); if (ci.mx-ci.mn!=(ni-1LL)*k){ printf("No ");continue; }sm=a1*ni+ni*(ni-1LL)/2LL*k; rm1=(UL)(ni*(ni-1LL))*(UL)a1*(UL)k+(UL)ni*usqr(a1)+ usqr(k)*(UL)getn(ni-1LL); rm2=(ni*(ni-1LL)%p*a1%p*k%p+ni*sqr(a1)%p+ sqr(k)*(getn(ni-1LL)%p)%p)%p; rm3=(ni*(ni-1LL)%p2*a1%p2*k%p2+ni*sqr2(a1)%p2+ sqr2(k)*(getn(ni-1LL)%p2)%p2)%p2; if (sm==ci.sm&&rm1==ci.rm1&&rm2==ci.rm2&&rm3==ci.rm3){ ++cnt;printf("Yes "); }else printf("No "); } } }
正解似乎是：考虑约束等差数列：（1）k=0，max=min；（2）k!=0：(max-min)/(r-l)=k,区间中无重复元素(记下当前i上ai的上一个位置pre，如果max pre<l就是满足的)，k|相邻两数的差的gcd(用线段树log^2)。（！！！）
bzoj4552 排序
题目大意：给一个1～n的全排列，m次部分排序（升/降），问q位置的数是什么。
思路：类似middle的做法，二分答案x，对于<x的赋成0，>=x的为1，m个操作相当于把区间内的0/1放到左边，用线段树区间修改，最后查询q位置是0/1，如果是0，说明答案比x小，否则答案>=x。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 100005 using namespace std; int in(){ char ch=getchar();int x=0; while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar(); }return x;} struct use{int sm,del;}tr[N<<2]; struct qu{int op,l,r;}ask[N]; int ai[N],n,m,xx,qq; use updata(use x,use y){ use c;c.del=-1; c.sm=x.sm+y.sm; return c;} void pushdown(int i,int l,int mid,int r){ if (tr[i].del==0){ tr[i<<1].sm=tr[i<<1|1].sm=0; tr[i<<1].del=tr[i<<1|1].del=0; }else{ tr[i<<1].sm=mid-l+1;tr[i<<1|1].sm=r-mid; tr[i<<1].del=tr[i<<1|1].del=1; }tr[i].del=-1; } void build(int i,int l,int r){ if (l==r){tr[i]=(use){ai[l]>=xx,-1};return;} int mid=(l+r)>>1; build(i<<1,l,mid);build(i<<1|1,mid+1,r); tr[i]=updata(tr[i<<1],tr[i<<1|1]); } int qsm(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr) return tr[i].sm; int sm=0,mid=(l+r)>>1; if (tr[i].del>=0) pushdown(i,l,mid,r); if (ll<=mid) sm+=qsm(i<<1,l,mid,ll,rr); if (rr>mid) sm+=qsm(i<<1|1,mid+1,r,ll,rr); return sm;} void tch(int i,int l,int r,int ll,int rr,int x){ if (ll<=l&&r<=rr){ tr[i].sm=(r-l+1)*x;tr[i].del=x; return; }int mid=(l+r)>>1; if (tr[i].del>=0) pushdown(i,l,mid,r); if (ll<=mid) tch(i<<1,l,mid,ll,rr,x); if (rr>mid) tch(i<<1|1,mid+1,r,ll,rr,x); tr[i]=updata(tr[i<<1],tr[i<<1|1]); } bool judge(int x){ int i,s0,s1,l,r;xx=x; build(1,1,n); for (i=1;i<=m;++i){ l=ask[i].l;r=ask[i].r; s1=qsm(1,1,n,l,r); s0=r-l+1-s1; if (ask[i].op){ if (s1) tch(1,1,n,l,l+s1-1,1); if (s0) tch(1,1,n,r-s0+1,r,0); }else{ if (s0) tch(1,1,n,l,l+s0-1,0); if (s1) tch(1,1,n,r-s1+1,r,1); } }return qsm(1,1,n,qq,qq); } int main(){ int i,l,r,mid,ans;n=in();m=in(); for (i=1;i<=n;++i) ai[i]=in(); for (i=1;i<=m;++i) ask[i]=(qu){in(),in(),in()}; qq=in();l=1;r=n; while(l<=r){ mid=(l+r)>>1; if (!judge(mid)) r=mid-1; else{ans=mid;l=mid+1;} }printf("%d ",ans); }
Mex
题目大意：给定一个长度为n的序列，求所有子序列的mex的和。
思路：对于l～r中的所有l开头的子序列，如果左端点的值x，变成l+1开头的，l+1～next[x]-1的位置的>x的值都变为x（！！！），可以用线段树维护。这道题目中可以用线段树保存到i的序列的mex，从左到右扫l开头的，这样的mex是单调不减的，可以查>x的时候在线段树上二分一下，然后区间赋值。累计答案。
注意：（1）修改的时候pushdown；
（2）所有左端点都要累计答案；
（3）一些边界的情况。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define N 200005 #define LL long long using namespace std; int in(){ char ch=getchar();int x=0; while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar(); }return x;} struct use{int mx,del;LL sm;}tr[N<<2]; int ai[N],point[N],next[N],n,bi[N],se[N<<2]; bool vi[N]; void buise(int i,int l,int r){ if (l==r){se[i]=l;return;} int mid=(l+r)>>1; buise(i<<1,l,mid);buise(i<<1|1,mid+1,r); se[i]=min(se[i<<1],se[i<<1|1]); } void sch(int i,int l,int r,int x){ if (l==r){se[i]=n+1;return;} int mid=(l+r)>>1; if (x<=mid) sch(i<<1,l,mid,x); else sch(i<<1|1,mid+1,r,x); se[i]=min(se[i<<1],se[i<<1|1]); } use updata(use a,use b){ use c;c.del=-1; c.mx=max(a.mx,b.mx); c.sm=a.sm+b.sm; return c; } void pushdown(int i,int l,int mid,int r){ int x=tr[i].del; tr[i<<1].del=tr[i<<1|1].del=x; tr[i<<1].mx=tr[i<<1|1].mx=x; tr[i<<1].sm=(LL)(mid-l+1)*x; tr[i<<1|1].sm=(LL)(r-mid)*x; } void build(int i,int l,int r){ if (l==r){tr[i]=(use){bi[l],-1,(LL)bi[l]};return;} int mid=(l+r)>>1; build(i<<1,l,mid);build(i<<1|1,mid+1,r); tr[i]=updata(tr[i<<1],tr[i<<1|1]); } void tch(int i,int l,int r,int x,int y){ if (l==r){tr[i]=(use){y,-1,(LL)y};return;} int mid=(l+r)>>1; if (tr[i].del>=0) pushdown(i,l,mid,r); if (x<=mid) tch(i<<1,l,mid,x,y); else tch(i<<1|1,mid+1,r,x,y); tr[i]=updata(tr[i<<1],tr[i<<1|1]); } void qch(int i,int l,int r,int ll,int rr,int x){ if (ll<=l&&r<=rr){ tr[i]=(use){x,x,(LL)(r-l+1)*x}; return; }int mid=(l+r)>>1; if (tr[i].del>=0) pushdown(i,l,mid,r); if (ll<=mid) qch(i<<1,l,mid,ll,rr,x); if (rr>mid) qch(i<<1|1,mid+1,r,ll,rr,x); tr[i]=updata(tr[i<<1],tr[i<<1|1]); } int getl(int i,int l,int r,int x){ if (l==r) return l; int mid=(l+r)>>1; if (tr[i].del>=0) pushdown(i,l,mid,r); if (tr[i<<1].mx<x) return getl(i<<1|1,mid+1,r,x); else return getl(i<<1,l,mid,x); } int main(){ int i,j;LL ans; while(scanf("%d",&n)==1){ buise(1,0,n); point[0]=n+1; for (i=1;i<=n;++i){ ai[i]=in(); if (ai[i]<=n) sch(1,0,n,ai[i]); bi[i]=se[1]; point[i]=n+1; }build(1,1,n); ans=tr[1].sm; for (i=n;i;--i){ if (ai[i]>n) continue; next[i]=point[ai[i]]; point[ai[i]]=i; }for (i=1;i<n;++i){ if (ai[i]>tr[1].mx){ ans+=tr[1].sm;continue; }j=getl(1,1,n,ai[i]); if (max(j,i+1)<next[i]) qch(1,1,n,max(j,i+1),next[i]-1,ai[i]); tch(1,1,n,i,0); ans+=tr[1].sm; }printf("%I64d ",ans); } }
bzoj3878 奇怪的计算器
题目大意：给出n个运算（+、-、*、@(表示+a*x，x是最开始运算的数，a是当前操作读入的数)），计算器的上下边界l、r，和q次询问的x，其中如果某次操作不在[l,r]，就赋成最近的边界的值，问q次的答案。
思路：离线。对x排序之后，这些操作不会改变相对大小，进行n个操作，每次都是在线段树上二分出区间赋值和区间+-*、系数的位置，然后放标记。这里不用开longlong，因为如果某次操作暴int，可以看做在%2^31下的操作，最终结果在[l,r]，不影响答案。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 100005 #define LL long long using namespace std; char chin(){ char ch=getchar(); while(ch!='+'&&ch!='-'&&ch!='*'&&ch!='@') ch=getchar(); return ch;} int in(){ char ch=getchar();int x=0; while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar(); }return x;} struct use{ int po,v; bool operator<(const use&x)const{return (v<x.v);} }ai[N]; struct oper{char ch;int a;}qi[N]; struct tree{int mn,mx,qj,qc,qf,qx;}tr[N<<2]; int ans[N],pl; tree updata(tree x,tree y){ tree c;c.qj=c.qf=c.qx=0;c.qc=1; c.mn=min(x.mn,y.mn); c.mx=max(x.mx,y.mx); return c;} void pji(int i,int x){ if (tr[i].qf) tr[i].qf+=x; else tr[i].qj+=x; tr[i].mx+=x;tr[i].mn+=x; } void pfu(int i,int x){ tr[i].qj=tr[i].qx=0;tr[i].qc=1; tr[i].qf=tr[i].mn=tr[i].mx=x; } void pch(int i,int x){ if (tr[i].qf) tr[i].qf*=x; else{tr[i].qc*=x;tr[i].qj*=x;tr[i].qx*=x;} tr[i].mx*=x;tr[i].mn*=x; } void pxi(int i,int l,int r,int x){ tr[i].qx+=x; tr[i].mn+=x*ai[l].v; tr[i].mx+=x*ai[r].v; } void pushdown(int i,int l,int r){ if (tr[i].qc>1){ pch(i<<1,tr[i].qc); pch(i<<1|1,tr[i].qc); tr[i].qc=1; }if (tr[i].qj){ pji(i<<1,tr[i].qj); pji(i<<1|1,tr[i].qj); tr[i].qj=0; }if (tr[i].qf){ pfu(i<<1,tr[i].qf); pfu(i<<1|1,tr[i].qf); tr[i].qf=0; }if (tr[i].qx){ int mid=(l+r)>>1; pxi(i<<1,l,mid,tr[i].qx); pxi(i<<1|1,mid+1,r,tr[i].qx); tr[i].qx=0; } } void build(int i,int l,int r){ if (l==r){ tr[i]=(tree){ai[l].v,ai[l].v,0,1,0,0}; return; }int mid=(l+r)>>1; build(i<<1,l,mid);build(i<<1|1,mid+1,r); tr[i]=updata(tr[i<<1],tr[i<<1|1]); } void ges(int i,int l,int r,int x,int y){ if (l==r){ if (tr[i].mx+y*ai[l].v<=x) pl=l; return; }int mid=(l+r)>>1; pushdown(i,l,r); if (tr[i<<1].mx+y*ai[mid].v<=x){pl=mid;ges(i<<1|1,mid+1,r,x,y);} else ges(i<<1,l,mid,x,y); } void gre(int i,int l,int r,int x){ if (l==r){ if (tr[i].mx>=x) pl=l; return; }int mid=(l+r)>>1; pushdown(i,l,r); if (tr[i<<1|1].mn>=x){pl=mid+1;gre(i<<1,l,mid,x);} else gre(i<<1|1,mid+1,r,x); } void tji(int i,int l,int r,int ll,int rr,int x){ if (ll<=l&&r<=rr){pji(i,x);return;} int mid=(l+r)>>1; pushdown(i,l,r); if (ll<=mid) tji(i<<1,l,mid,ll,rr,x); if (rr>mid) tji(i<<1|1,mid+1,r,ll,rr,x); tr[i]=updata(tr[i<<1],tr[i<<1|1]); } void tfu(int i,int l,int r,int ll,int rr,int x){ if (ll<=l&&r<=rr){pfu(i,x);return;} int mid=(l+r)>>1; pushdown(i,l,r); if (ll<=mid) tfu(i<<1,l,mid,ll,rr,x); if (rr>mid) tfu(i<<1|1,mid+1,r,ll,rr,x); tr[i]=updata(tr[i<<1],tr[i<<1|1]); } void tch(int i,int l,int r,int ll,int rr,int x){ if (ll<=l&&r<=rr){pch(i,x);return;} int mid=(l+r)>>1; pushdown(i,l,r); if (ll<=mid) tch(i<<1,l,mid,ll,rr,x); if (rr>mid) tch(i<<1|1,mid+1,r,ll,rr,x); tr[i]=updata(tr[i<<1],tr[i<<1|1]); } void txi(int i,int l,int r,int ll,int rr,int x){ if (ll<=l&&r<=rr){pxi(i,l,r,x);return;} int mid=(l+r)>>1; pushdown(i,l,r); if (ll<=mid) txi(i<<1,l,mid,ll,rr,x); if (rr>mid) txi(i<<1|1,mid+1,r,ll,rr,x); tr[i]=updata(tr[i<<1],tr[i<<1|1]); } void geta(int i,int l,int r){ if (l==r){ans[ai[l].po]=tr[i].mx;return;} int mid=(l+r)>>1; pushdown(i,l,r); geta(i<<1,l,mid);geta(i<<1|1,mid+1,r); } int main(){ int n,q,i,l,r,a; n=in();l=in();r=in(); for (i=1;i<=n;++i) qi[i]=(oper){chin(),in()}; q=in(); for (i=1;i<=q;++i) ai[i]=(use){i,in()}; sort(ai+1,ai+q+1); build(1,1,q); for (i=1;i<=n;++i){ a=qi[i].a; if (qi[i].ch=='+'){ pl=0;ges(1,1,q,r-a,0); if (pl) tji(1,1,q,1,pl,a); if (pl<q) tfu(1,1,q,pl+1,q,r); }if (qi[i].ch=='-'){ pl=q+1;gre(1,1,q,l+a); if (pl>1) tfu(1,1,q,1,pl-1,l); if (pl<=q) tji(1,1,q,pl,q,-a); }if (qi[i].ch=='*'){ pl=0;ges(1,1,q,r/a,0); if (pl) tch(1,1,q,1,pl,a); if (pl<q) tfu(1,1,q,pl+1,q,r); }if (qi[i].ch=='@'){ pl=0;ges(1,1,q,r,a); if (pl) txi(1,1,q,1,pl,a); if (pl<q) tfu(1,1,q,pl+1,q,r); } }geta(1,1,q); for (i=1;i<=q;++i) printf("%d ",ans[i]); }
bzoj4378 Logistyka
题目大意：有n个数，一开始都是0。支持：1）修改某个位置的数；2）能否进行s次操作，每次都是选c个正数-1。
思路：每次查询相当于选出c个>=s的数，>=s的可以不用考虑，直接从c里减掉，对于其他的可以任意组合，因为每个都<s，所以一定可以通过某种方式使得每次操作每个数只做一次，所以直接看<s的数的和是否满足>=c‘*s就可以了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 1000005 #define LL long long using namespace std; int in(){ char ch=getchar();int x=0; while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar(); }return x;} char chin(){ char ch=getchar(); while(ch<'A'||ch>'Z') ch=getchar(); return ch;} int ci[N],cz=0,cnt[N]={0},ai[N]; struct use{int k,a,b;}bi[N]; struct tree{int v;LL sm;}tr[N<<2]; tree updata(tree a,tree b){return (tree){a.v+b.v,a.sm+b.sm};} void build(int i,int l,int r){ if (l==r){ tr[i]=(tree){cnt[l],(LL)cnt[l]*ci[l]}; return; }int mid=(l+r)>>1; build(i<<1,l,mid);build(i<<1|1,mid+1,r); tr[i]=updata(tr[i<<1],tr[i<<1|1]); } void tch(int i,int l,int r,int x){ if (l==r){ tr[i]=(tree){cnt[l],(LL)cnt[l]*ci[l]}; return; }int mid=(l+r)>>1; if (x<=mid) tch(i<<1,l,mid,x); else tch(i<<1|1,mid+1,r,x); tr[i]=updata(tr[i<<1],tr[i<<1|1]); } int ask(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr) return tr[i].v; int sm=0,mid=(l+r)>>1; if (ll<=mid) sm+=ask(i<<1,l,mid,ll,rr); if (rr>mid) sm+=ask(i<<1|1,mid+1,r,ll,rr); return sm; } LL qsm(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr) return tr[i].sm; LL sm=0LL;int mid=(l+r)>>1; if (ll<=mid) sm+=qsm(i<<1,l,mid,ll,rr); if (rr>mid) sm+=qsm(i<<1|1,mid+1,r,ll,rr); return sm; } int main(){ int i,j,n,m;LL sm;n=in();m=in(); for (i=1;i<=m;++i){ bi[i]=(use){(chin()=='Z'),in(),in()}; ci[++cz]=bi[i].b; }ci[++cz]=0; sort(ci+1,ci+cz+1); cz=unique(ci+1,ci+cz+1)-ci-1; cnt[1]=n;build(1,1,cz); for (i=1;i<=n;++i) ai[i]=1; for (i=1;i<=m;++i){ if (!bi[i].k){ j=ai[bi[i].a]; ai[bi[i].a]=upper_bound(ci+1,ci+cz+1,bi[i].b)-ci-1; --cnt[j];tch(1,1,cz,j); ++cnt[ai[bi[i].a]];tch(1,1,cz,ai[bi[i].a]); }else{ j=upper_bound(ci+1,ci+cz+1,bi[i].b)-ci-1; bi[i].a-=ask(1,1,cz,j,cz); if (j>1) sm=qsm(1,1,cz,1,j-1); else sm=0LL; if (sm>=(LL)bi[i].a*bi[i].b) printf("TAK "); else printf("NIE "); } } }
bzoj4384 [POI2015]Trzy wieże
题目大意：给定一个只有B、C、S组成的字符串，求最长的一个子段满足任意两种字母数量不同或者只有一种字母。
思路：一个和两个字符的情况都可以扫一遍解决。三个的时候，求出前缀和sm0、sm1、sm2，如果令x=sm0-sm1,y=sm1-sm2,z=sm2-sm0，就相当于求编号差最大的两个任意坐标不相同的编号差，对x排序，按y建线段树，处理l~r的最大（小）编号和与最大（小）编号的z不一样的次大（小）编号，更新答案。
有一些剪枝：1）线段树查区间的时候，如果区间的最大最小值更新出的答案都不如ans优就可以了返回；
2）如果这个点所在位置做为左右端点的最大值都不如ans优，就可以不用插入和查询了。
3）宏定义快。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 1000005 #define inf 2100000000 #define MAX(x,y) (x<y ? y : x) #define MIN(x,y) (x<y ? x : y) #define mid (l+r)/2 #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r using namespace std; inline int chin(){ char ch=getchar(); while(ch<'A'||ch>'Z') ch=getchar(); return (ch=='S' ? 2 : (ch=='C')); } inline int ab(int x){return (x<0 ? -x : x);} struct use{ int p,x,y,z; bool operator<(const use&xx)const{return x<xx.x;} }ai[N]; struct seg{int mx,cmx,mn,cmn;}tr[N<<2],al; int bi[N],sm[3]={0},ci[N<<1]={0},cz=0,p,su[N][3],ans=0; inline int gmx(int x){return (x<0 ? -1 : ai[x].p);} inline int gmn(int x){return (x<0 ? inf : ai[x].p);} seg updata(seg x,seg y){ seg c;int yy;c=x; if (y.mx>=0){ yy=y.mx; if (ai[yy].p>gmx(c.mx)){ if (ai[c.mx].z!=ai[yy].z) c.cmx=c.mx; c.mx=yy; if (y.cmx>=0){ yy=y.cmx; if (ai[yy].z!=ai[c.mx].z&&ai[yy].p>gmx(c.cmx)) c.cmx=yy; } }else{ if (ai[yy].z!=ai[c.mx].z&&ai[yy].p>gmx(c.cmx)) c.cmx=yy; else if (y.cmx>=0){ yy=y.cmx; if (ai[yy].z!=ai[c.mx].z&&ai[yy].p>gmx(c.cmx)) c.cmx=yy; } } }if (y.mn>=0){ yy=y.mn; if (ai[yy].p<gmn(c.mn)){ if (ai[c.mn].z!=ai[yy].z) c.cmn=c.mn; c.mn=yy; if (y.cmn>=0){ yy=y.cmn; if (ai[yy].z!=ai[c.mn].z&&ai[yy].p<gmn(c.cmn)) c.cmn=yy; } }else{ if (ai[yy].z!=ai[c.mn].z&&ai[yy].p<gmn(c.cmn)) c.cmn=yy; else if (y.cmn>=0){ yy=y.cmn; if (ai[yy].z!=ai[c.mn].z&&ai[yy].p<gmn(c.cmn)) c.cmn=yy; } } }return c; } void tch(int i,int l,int r,int x,int y){ if (l==r){ if (ai[y].p>gmx(tr[i].mx)){ if (ai[tr[i].mx].z!=ai[y].z) tr[i].cmx=tr[i].mx; tr[i].mx=y; }else{ if (ai[y].z!=ai[tr[i].mx].z&&ai[y].p>gmx(tr[i].cmx)) tr[i].cmx=y; }if (ai[y].p<gmn(tr[i].mn)){ if (ai[tr[i].mn].z!=ai[y].z) tr[i].cmn=tr[i].mn; tr[i].mn=y; }else{ if (ai[y].z!=ai[tr[i].mn].z&&ai[y].p<gmn(tr[i].cmn)) tr[i].cmn=y; }return; }if (x<=mid) tch(lson,x,y); else tch(rson,x,y); tr[i]=updata(tr[i<<1],tr[i<<1|1]); } void ask(int i,int l,int r,int ll,int rr){ if (tr[i].mx<0) return; if (max(ab(p-ai[tr[i].mx].p),ab(p-ai[tr[i].mn].p))<=ans) return; if (ll<=l&&r<=rr){al=updata(al,tr[i]);return;} if (ll<=mid) ask(lson,ll,rr); if (rr>mid) ask(rson,ll,rr); } int main(){ int n,i,j,k,y; scanf("%d",&n); ai[0]=(use){0,0,0,0}; for (i=1;i<=n;++i){ ++sm[bi[i]=chin()]; ai[i]=(use){i,sm[0]-sm[1],sm[1]-sm[2],sm[2]-sm[0]}; ci[sm[1]-sm[2]+n+1]=1; }for (i=1;i<=n;i=j+1){ for (j=i;j<n&&bi[j+1]==bi[j];++j); ans=MAX(ans,j-i+1); }sm[0]=sm[1]=sm[2]=0; su[0][0]=su[0][1]=su[0][2]=0; for (i=1;i<=n;++i){ su[i][0]=su[i-1][0]; su[i][1]=su[i-1][1]; su[i][2]=su[i-1][2]; ++su[i][bi[i]]; j=sm[bi[i]];sm[bi[i]]=i; if (!bi[i]) k=(su[i][1]-su[j][1])-(su[i][2]-su[j][2]); else if (bi[i]==1) k=(su[i][0]-su[j][0])-(su[i][2]-su[j][2]); else k=(su[i][0]-su[j][0])-(su[i][1]-su[j][1]); if (k==0) ans=MAX(ans,i-j-2); else ans=MAX(ans,i-j-1); }sort(ai,ai+n+1); ci[0]=1; for (i=1;i<=(n<<1);++i) if (ci[i]) ci[++cz]=i-n-1; memset(tr,-1,sizeof(tr)); for (i=0;i<=n;i=j+1){ for (j=i;j<n&&ai[j+1].x==ai[j].x;++j); for (k=i;k<=j;++k){ p=ai[k].p; if (MAX(n-p,p)<=ans) continue; y=ai[k].y=upper_bound(ci+1,ci+cz+1,ai[k].y)-ci-1; al=(seg){-1,-1,-1,-1}; if (y>1) ask(1,1,cz,1,y-1); if (y<cz) ask(1,1,cz,y+1,cz); if (al.mx>=0){ if (ai[al.mx].z!=ai[k].z) ans=max(ans,ab(p-ai[al.mx].p)); else if (al.cmx>=0) ans=max(ans,ab(p-ai[al.cmx].p)); if (ai[al.mn].z!=ai[k].z) ans=max(ans,ab(p-ai[al.mn].p)); else if (al.cmn>=0) ans=max(ans,ab(p-ai[al.cmn].p)); } }for (k=i;k<=j;++k){ if (MAX(n-ai[k].p,ai[k].p)<=ans) continue; tch(1,1,cz,ai[k].y,k); } }printf("%d ",ans); }
bzoj4631 踩气球
题目大意：n个盒子，有ai个球，m个孩子，每个孩子高兴的条件是li~ri的ai=0。q次操作，每次操作给一个ai -1，输出每次操作后的高兴的孩子个数。强制在线。
思路：每次只改变一个点，考虑这个点改变后影响的孩子，就是这个点连续出去为0的那一段中之前没有高兴的孩子。用链表维护0的连续段，每次相当于右端点在l~r中且左端点在l~r中的孩子，按右端点排序之后，左端点取最大值建树，每次相当于查询1~x中的最大值，如果>=l就赋成0之后继续做。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define N 100005 #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r using namespace std; int in(){ char ch=getchar();int x=0; while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar(); }return x;} struct use{ int l,r; bool operator<(const use&x)const{return r<x.r;} }bi[N]; struct seg{int mx,mp;}tr[N<<2],ci; int ai[N],pre[N],suc[N],gi[N]={0}; seg updata(seg x,seg y){return (x.mx>y.mx ? x : y);} void build(int i,int l,int r){ if (l==r){tr[i]=(seg){bi[l].l,l};return;} int mid=(l+r)>>1; build(lson);build(rson); tr[i]=updata(tr[i<<1],tr[i<<1|1]); } void ask(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr){ if (ll==l) ci=tr[i]; else ci=updata(ci,tr[i]); return; }int mid=(l+r)>>1; if (ll<=mid) ask(lson,ll,rr); if (rr>mid) ask(rson,ll,rr); } void tch(int i,int l,int r,int x){ if (l==r){tr[i].mx=0;return;} int mid=(l+r)>>1; if (x<=mid) tch(lson,x); else tch(rson,x); tr[i]=updata(tr[i<<1],tr[i<<1|1]); } int main(){ int n,m,q,i,j,l,r,la=0; n=in();m=in(); for (i=1;i<=n;++i){ ai[i]=in(); pre[i]=i-1;suc[i]=i+1; }pre[1]=0;suc[n]=n+1; for (i=1;i<=m;++i){ bi[i]=(use){in(),in()}; }sort(bi+1,bi+m+1); for (i=1,j=1;i<=n;++i){ while(bi[j].r<=i) ++j; gi[i]=j-1; }build(1,1,m);q=in(); while(q--){ i=(in()+la-1)%n+1;--ai[i]; if (!ai[i]){ suc[pre[i]]=suc[i]; pre[suc[i]]=pre[i]; l=pre[i]+1;r=suc[i]-1; if (gi[r]){ ask(1,1,m,1,gi[r]); while(ci.mx>=l){ tch(1,1,m,ci.mp);++la; ask(1,1,m,1,gi[r]); } } }printf("%d ",la); } }
四分树
bzoj3242 魔幻棋盘（！）
题目大意：给出一个矩形，支持操作：1）询问过定点(x,y)的矩形中数的gcd；2）给某个矩形中的数都+c。保证矩形中数始终为正整数。
思路：gcd(a,b,c)=gcd(gcd(a,b),gcd(a,c))=gcd(gcd(a,b-a),gcd(a,c-a))=gcd(a,gcd(b-a,c-a))=gcd(a,gcd(b-a,c-b))，考虑一维的时候，差分之后的gcd不会变，区间加变成了两个单点改变，查询的时候是l+1~r的差的gcd和ai[l]的gcd。二维的时候，证明相似，做二维差分，最后答案是一个矩形、单点、两条直线的gcd，两条直线可以取过(x,y)的（可以避免多条直线的修改），单点是(x,y)，四分树维护矩形的，两个线段树维护直线(行/列)的，单点的全局delta维护一下。
注意：1）gcd(a,b)=gcd(a,b-a)，gcd(a,b)=gcd(a,-b)；
2）查询的时候，两条直线一定是过(x,y)的。
3）四分树中查询的区间可能出现x1>x2或者y1>y2的情况（某条直线再去划分的时候，相等的那一维会出问题），所以要及时return。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 500005 #define M 4000005 #define nn 2000005 #define LL long long #define m1 (x1+x2)/2 #define m2 (y1+y2)/2 #define mid (l+r)/2 using namespace std; inline int in(){ char ch=getchar();int x=0,f=1; while((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar(); }return x*f;} inline LL lin(){ char ch=getchar();LL x=0LL,f=1LL; while((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); if (ch=='-'){f=-1LL;ch=getchar();} while(ch>='0'&&ch<='9'){ x=x*10LL+ch-'0';ch=getchar(); }return x*f;} struct seg{int ch[4];LL v;}se[M]; struct tree{int ch[2];LL v;}tb[nn],tc[nn]; int n,m,br[N]={0},cr[N]={0},bt=0,ct=0,st=0,sr=0; LL ai[N]={0},bi[N],ci[N],di[N]; inline int idx(int i,int j){return (i-1)*m+j;} inline LL gcd(LL a,LL b){ if (a<0LL) a=-a; if (b<0LL) b=-b; return (!b ? a : gcd(b,a%b)); } void build(int &i,int x1,int x2,int y1,int y2){ if (x1>x2||y1>y2) return; i=++st; if (x1==x2&&y1==y2){se[i].v=di[idx(x1,y1)];return;} build(se[i].ch[0],x1,m1,y1,m2);build(se[i].ch[1],m1+1,x2,y1,m2); build(se[i].ch[2],x1,m1,m2+1,y2);build(se[i].ch[3],m1+1,x2,m2+1,y2); se[i].v=gcd(se[se[i].ch[0]].v,gcd(se[se[i].ch[1]].v, gcd(se[se[i].ch[2]].v,se[se[i].ch[3]].v))); } void tuilb(int &i,int l,int r,int x){ i=++bt; if (l==r){tb[i].v=bi[idx(x,l)];return;} tuilb(tb[i].ch[0],l,mid,x); tuilb(tb[i].ch[1],mid+1,r,x); tb[i].v=gcd(tb[tb[i].ch[0]].v,tb[tb[i].ch[1]].v); } void tuilc(int &i,int l,int r,int x){ i=++ct; if (l==r){tc[i].v=ci[idx(l,x)];return;} tuilc(tc[i].ch[0],l,mid,x); tuilc(tc[i].ch[1],mid+1,r,x); tc[i].v=gcd(tc[tc[i].ch[0]].v,tc[tc[i].ch[1]].v); } inline bool bin(int x1,int x2,int y1,int y2,int a1,int a2,int b1,int b2){ return (a1<=x1&&x2<=a2&&b1<=y1&&y2<=b2); } LL askd(int i,int x1,int x2,int y1,int y2,int a1,int a2,int b1,int b2){ if (!i) return 0LL; if (bin(x1,x2,y1,y2,a1,a2,b1,b2)) return se[i].v; LL sm=0LL; if (a1<=m1&&b1<=m2) sm=gcd(sm,askd(se[i].ch[0],x1,m1,y1,m2,a1,a2,b1,b2)); if (a2>m1&&b1<=m2) sm=gcd(sm,askd(se[i].ch[1],m1+1,x2,y1,m2,a1,a2,b1,b2)); if (a1<=m1&&b2>m2) sm=gcd(sm,askd(se[i].ch[2],x1,m1,m2+1,y2,a1,a2,b1,b2)); if (a2>m1&&b2>m2) sm=gcd(sm,askd(se[i].ch[3],m1+1,x2,m2+1,y2,a1,a2,b1,b2)); return sm; } LL askb(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr) return tb[i].v; LL sm=0LL; if (ll<=mid) sm=gcd(sm,askb(tb[i].ch[0],l,mid,ll,rr)); if (rr>mid) sm=gcd(sm,askb(tb[i].ch[1],mid+1,r,ll,rr)); return sm; } LL askc(int i,int l,int r,int ll,int rr){ if (ll<=l&&r<=rr) return tc[i].v; LL sm=0LL; if (ll<=mid) sm=gcd(sm,askc(tc[i].ch[0],l,mid,ll,rr)); if (rr>mid) sm=gcd(sm,askc(tc[i].ch[1],mid+1,r,ll,rr)); return sm; } void tch(int i,int x1,int x2,int y1,int y2,int x,int y,LL c){ if (x1==x2&&y1==y2){se[i].v+=c;return;} if (x<=m1&&y<=m2) tch(se[i].ch[0],x1,m1,y1,m2,x,y,c); if (x>m1&&y<=m2) tch(se[i].ch[1],m1+1,x2,y1,m2,x,y,c); if (x<=m1&&y>m2) tch(se[i].ch[2],x1,m1,m2+1,y2,x,y,c); if (x>m1&&y>m2) tch(se[i].ch[3],m1+1,x2,m2+1,y2,x,y,c); se[i].v=gcd(se[se[i].ch[0]].v,gcd(se[se[i].ch[1]].v, gcd(se[se[i].ch[2]].v,se[se[i].ch[3]].v))); } void bch(int i,int l,int r,int x,LL y){ if (l==r){tb[i].v+=y;return;} if (x<=mid) bch(tb[i].ch[0],l,mid,x,y); else bch(tb[i].ch[1],mid+1,r,x,y); tb[i].v=gcd(tb[tb[i].ch[0]].v,tb[tb[i].ch[1]].v); } void cch(int i,int l,int r,int x,LL y){ if (l==r){tc[i].v+=y;return;} if (x<=mid) cch(tc[i].ch[0],l,mid,x,y); else cch(tc[i].ch[1],mid+1,r,x,y); tc[i].v=gcd(tc[tc[i].ch[0]].v,tc[tc[i].ch[1]].v); } int main(){ int x,y,i,j,k,t,op,x1,x2,y1,y2; LL ans,dc=0LL,c; n=in();m=in();x=in();y=in();t=in(); for (i=1;i<=n;++i) for (j=1;j<=m;++j){ ai[k=idx(i,j)]=lin(); bi[k]=ai[k]-ai[k-1]; ci[k]=ai[k]-ai[max(0,k-m)]; di[k]=bi[k]-bi[max(0,k-m)]; }build(sr,1,n,1,m); for (i=1;i<=n;++i) tuilb(br[i],1,m,i); for (i=1;i<=m;++i) tuilc(cr[i],1,n,i); while(t--){ if (!(op=in())){ x1=x-in();y1=y-in(); x2=x+in();y2=y+in(); ans=ai[idx(x,y)]+dc; if (x2-x1) ans=gcd(ans,askc(cr[y],1,n,x1+1,x2)); if (y2-y1) ans=gcd(ans,askb(br[x],1,m,y1+1,y2)); if ((x2-x1)&&(y2-y1)) ans=gcd(ans,askd(sr,1,n,1,m,x1+1,x2,y1+1,y2)); printf("%I64d ",ans); }else{ x1=in();y1=in();x2=in();y2=in();c=lin(); if (x1<=x&&x<=x2&&y1<=y&&y<=y2) dc+=c; if (x1<=x&&x<=x2){ bch(br[x],1,m,y1,c); if (y2<m) bch(br[x],1,m,y2+1,-c); }if (y1<=y&&y<=y2){ cch(cr[y],1,n,x1,c); if (x2<n) cch(cr[y],1,n,x2+1,-c); }tch(sr,1,n,1,m,x1,y1,c); if (x2<n) tch(sr,1,n,1,m,x2+1,y1,-c); if (y2<m) tch(sr,1,n,1,m,x1,y2+1,-c); if (x2<n&&y2<m) tch(sr,1,n,1,m,x2+1,y2+1,c); } } }
按时间分治
bzoj4311 向量
题目大意：支持三种操作：（1）插入一个向量；（2）删除一个向量；（3）查询与某个向量点积最大值。
思路：按时间建线段树，每个向量出现的时间是一段区间，插入的时候按x排序之后就可以做到nlogn的维护凸包。查询的时候顺着一条路径往下走，并三分更新答案，查询的复杂度是nlog^2n的。空间是nlogn的。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define N 200005 #define LL long long #define inf 1000000000000000000LL using namespace std; struct point{LL x,y;}; struct use{ point p;int s,t; bool operator<(const use x)const{return p.x<x.p.x;} }ai[N]; struct uu{point p;int po;}ask[N]; vector<point>up[N<<2]; int n=0; LL mx; point operator-(point a,point b){return (point){a.x-b.x,a.y-b.y};} LL cross(point a,point b){return a.x*b.y-a.y*b.x;} LL dot(point a,point b){return a.x*b.x+a.y*b.y;} void getg(int i,point x){ int j;j=up[i].size(); while(j>1&&cross(up[i][j-1]-x,up[i][j-2]-x)<=0LL){ --j;up[i].pop_back(); }up[i].push_back(x); } void ins(int i,int l,int r,point x,int ll,int rr){ if (ll<=l&&r<=rr){getg(i,x);return;} int mid=(l+r)>>1; if (ll<=mid) ins(i<<1,l,mid,x,ll,rr); if (rr>mid) ins(i<<1|1,mid+1,r,x,ll,rr); } void getm(int i,point x){ int l,r,m1,m2; l=0;r=up[i].size()-1; while(l<=r){ if (r-l<=2){ if (r-l==0) mx=max(mx,dot(x,up[i][l])); if (r-l==1) mx=max(mx,max(dot(x,up[i][l]),dot(x,up[i][r]))); if (r-l==2) mx=max(mx,max(dot(x,up[i][l]), max(dot(x,up[i][l+1]),dot(x,up[i][r])))); break; }m1=l+(r-l)/3;m2=r-(r-l)/3; if (dot(x,up[i][m1])<dot(x,up[i][m2])) l=m1; else r=m2; } } void query(int i,int l,int r,point x,int y){ getm(i,x); if (l==r) return; int mid=(l+r)>>1; if (y<=mid) query(i<<1,l,mid,x,y); else query(i<<1|1,mid+1,r,x,y); } int main(){ int m,i,k,x,y,az=0;scanf("%d",&m); for (i=1;i<=m;++i){ scanf("%d",&k); if (k==1){ scanf("%d%d",&x,&y);++n; ai[n]=(use){(point){(LL)x,(LL)y},i,0}; }if (k==2){ scanf("%d",&x);ai[x].t=i; }if (k==3){ scanf("%d%d",&x,&y); ask[++az]=(uu){(point){(LL)x,(LL)y},i}; } }sort(ai+1,ai+n+1); for (i=1;i<=n;++i){ if (!ai[i].t) ai[i].t=m; ins(1,1,m,ai[i].p,ai[i].s,ai[i].t); }for (i=1;i<=az;++i){ mx=0; query(1,1,m,ask[i].p,ask[i].po); printf("%I64d ",mx); } }