Description
Input
Output
若干行，每行一个整数，表示对一个问题的回答。请按照输入中的顺序依次给出回答。
Sample Input
513-1-472A 2 4 -1 5B 1 5Sample Output
2Solution
差分然后线段树维护，对于修改操作，第一个和最后一个单独改，中间一段区间加就好了。
然后就是恶心到爆炸的询问。。
对于每个区间，记录\(s[0/1/2/3]\)，分别表示左右端点都不取，只取左端点，只取右端点，都取的最小段数。
由于合并时，每种情况都类似，这里只讲\(s[0]\)的更新。
考虑现在要合并\((l,mid),(mid+1,r)\)，由于这是个差分数组，所以原序列可以看作是在两个值之间，然后考虑\(mid\)和\(mid+1\)之间这个数的去向：
- 和前面合并，即
ans.s[0]=min(ans.s[0],x.s[2]+y.s[0]);，其中\(ans\)为合并后的信息，现在要合并\(x,y\)。 - 和后面合并，即
ans.s[0]=min(ans.s[0],x.s[0]+y.s[1]); - 同时和两边合并，即
ans.s[0]=min(ans.s[0],x.s[2]+y.s[1]-(x.r==y.l));，其中\(l\)为最左边的差分值，\(r\)同理。
具体细节自己注意下就好了。
#include<bits/stdc++.h>#define ll long long using namespace std; void read(int &x) { ???x=0;int f=1;char ch=getchar(); ???for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; ???for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;} void print(int x) { ???if(x<0) putchar('-'),x=-x; ???if(!x) return ;print(x/10),putchar(x%10+48);}void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}const int maxn = 2e5+10;int n;struct node {int s[4];ll l,r;};#define ls p<<1#define rs p<<1|1#define mid ((l+r)>>1)int a[maxn];node operator + (const node &x,const node &y) { ???node ans; ???ans.l=x.l,ans.r=y.r; ???ans.s[0]=min(x.s[2]+y.s[1]-(x.r==y.l),min(x.s[2]+y.s[0],x.s[0]+y.s[1])); ???ans.s[1]=min(x.s[3]+y.s[1]-(x.r==y.l),min(x.s[1]+y.s[1],x.s[3]+y.s[0])); ???ans.s[2]=min(x.s[2]+y.s[3]-(x.r==y.l),min(x.s[0]+y.s[3],x.s[2]+y.s[2])); ???ans.s[3]=min(x.s[3]+y.s[3]-(x.r==y.l),min(x.s[3]+y.s[2],x.s[1]+y.s[3])); ???return ans;}struct Segment_Tree { ???node tr[maxn<<2];int tag[maxn<<2]; ???void push_tag(int p,int v) {tr[p].l+=v,tr[p].r+=v,tag[p]+=v;} ???void pushdown(int p) { ???????if(!tag[p]) return ; ???????push_tag(ls,tag[p]),push_tag(rs,tag[p]); ???????tag[p]=0; ???} ???void modify(int p,int l,int r,int x,int y,int v) { ???????if(x<=l&&r<=y) return push_tag(p,v),void(); ???????pushdown(p); ???????if(x<=mid) modify(ls,l,mid,x,y,v); ???????if(y>mid) modify(rs,mid+1,r,x,y,v); ???????tr[p]=tr[ls]+tr[rs]; ???} ???node query(int p,int l,int r,int x,int y) { ???????if(x<=l&&r<=y) return tr[p]; ???????pushdown(p);node ans; ???????if(y<=mid) return ans=query(ls,l,mid,x,y); ???????else if(x>mid) return ans=query(rs,mid+1,r,x,y); ???????else return ans=query(ls,l,mid,x,y)+query(rs,mid+1,r,x,y); ???????tr[p]=tr[ls]+tr[rs]; ???????return ans; ???} ???void build(int p,int l,int r) { ???????if(l==r) { ???????????tr[p].s[1]=tr[p].s[2]=tr[p].s[3]=1;tr[p].s[0]=0; ???????????tr[p].l=tr[p].r=a[l+1]-a[l];return ; ???????}build(ls,l,mid),build(rs,mid+1,r),tr[p]=tr[ls]+tr[rs]; ???}}SGT;signed main() { ???read(n); ???for(int i=1;i<=n;i++) read(a[i]);SGT.build(1,1,n-1); ???int q;read(q); ???while(q--) { ???????char s[4];int x,y,A,b;scanf("%s",s+1);read(x),read(y); ???????if(s[1]=='A') { ???????????read(A),read(b); ???????????if(x>1) SGT.modify(1,1,n-1,x-1,x-1,A); ???????????if(y<n) SGT.modify(1,1,n-1,y,y,-A-(y-x)*b); ???????????if(x<y) SGT.modify(1,1,n-1,x,y-1,b); ???????} else { ???????????if(x==y) puts("1"); ???????????else write(SGT.query(1,1,n-1,x,y-1).s[3]); ???????} ???} ???return 0;}[bzoj1558] [JSOI2009]等差数列
原文地址：https://www.cnblogs.com/hbyer/p/10184216.html