Description
Input
Output
若干行，每行一个整数，表示对一个问题的回答。请按照输入中的顺序依次给出回答。
Sample Input
5
1
3
-1
-4
7
2
A 2 4 -1 5
B 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;
}