难度虚高。
看到修改 + 区间查询 ， 不难想到 线段树 。
首先我们可以考虑维护 差分序列 而不是原序列。
那么一个等差数列长这个样子 ： x y y y …
那么想到充分利用首项，考虑从后往前贪心，在一堆相同的后缀前面再塞一个不同的数。
那么怎么表示一个区间的状态呢 ？ 我们发现只有两种情况。
- 前缀剩了 y y y …
- 不剩
剩余状态设计我们还要考虑是否挖掉右端点 （因为要抵消），需要用不同的 dp 值来存。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
//对于首位的情况特殊考虑
int n,m,v[N],cf[N];
inline int read() {
int x=0,f=1; char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*f;
}
struct node{
int u,d;
int c[2],val[2];
ll dat,vl,vr;
}t[N<<2];
node merge(node x,node y) {
node z;
z.dat=0;
z.vl=x.vl,z.vr=y.vr;
z.u=x.u,z.d=y.d;
if(x.vr!=y.vl) {
z.val[0]=y.val[0]+((y.c[0])?x.val[0]+1:x.val[1]);
z.c[0]=x.c[y.c[0]^1];
z.val[1]=y.val[1]+((y.c[1])?x.val[0]+1:x.val[1]);
z.c[1]=x.c[y.c[1]^1];
}
else {
z.val[0]=y.val[0]+((y.c[0])?x.val[1]+1:x.val[1]);
z.c[0]=x.c[1];
z.val[1]=y.val[1]+((y.c[1])?x.val[1]+1:x.val[1]);
z.c[1]=x.c[1];
}
return z;
}
void add(int p,ll dat) {
t[p].dat+=dat,t[p].vl+=dat,t[p].vr+=dat;
}
void pushdown(int p) {
add(p<<1,t[p].dat),add(p<<1|1,t[p].dat),t[p].dat=0;
}
void upd(int p,int l,int r,int ql,int qr,ll dat) {
// printf("%d %d %d %d %lld\n",l,r,ql,qr,dat);
if(ql>qr || qr < 1 || ql > n) return ;
if(ql<=l&&r<=qr) {
add(p,dat); return;
}
pushdown(p);
int mid=(l+r)/2;
if(ql<=mid) upd(p<<1,l,mid,ql,qr,dat);
if(mid<qr) upd(p<<1|1,mid+1,r,ql,qr,dat);
t[p]=merge(t[p<<1],t[p<<1|1]);
}
void init(int p,int l) {
t[p].u=t[p].d=l;
t[p].vl=t[p].vr=cf[l];
t[p].c[1]=1;
}
void build(int p,int l,int r) {
if(l==r) {
init(p,l); return;
}
int mid=(l+r)/2;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
t[p]=merge(t[p<<1],t[p<<1|1]);
}
node qry(int p,int l,int r,int ql,int qr) {
if(ql<=l&&r<=qr) return t[p];
pushdown(p);
int mid=(l+r)/2;
if(qr<=mid) return qry(p<<1,l,mid,ql,qr);
else if(mid<qr) return qry(p<<1|1,mid+1,r,ql,qr);
else return merge(qry(p<<1,l,mid,ql,mid),qry(p<<1|1,mid+1,r,mid+1,qr));
}
char op[10];
int main() {
// freopen("data.in","r",stdin);
n=read();
for(int i=1;i<=n;i++) v[i]=read();
for(int i=1;i<=n;i++) cf[i]=v[i]-v[i-1];
build(1,1,n);
m=read();
for(int i=1;i<=m;i++) {
scanf("%s",op);
if(op[0]=='A') {
int l=read(),r=read();
ll a=read(),b=read();
upd(1,1,n,l,l,a);
upd(1,1,n,l+1,r,b);
upd(1,1,n,r+1,r+1,-(a+(r-l)*b));
}
else {
int l=read(),r=read();
node tmp=qry(1,1,n,l,r);
printf("%d\n",r-l+1-tmp.val[1]);
}
}
}
