注意到边界格数\(=\)（左上）轮廓线长度\(-1=\)（右下）轮廓线长度\(-1\)
问题即在整体（右下）轮廓线中选连续\(q+1\)条，满足第一条为竖线且最后一条为横线
将两者分别标记为\(01\)，即对于序列\(\{a_{p}\}\)，判断是否存在\(a_{i}=0\)且\(a_{i+q}=1\)
注意到\(a_{0}=0,a_{p}=1\)且\(q\mid p\)，即可在\(a_{iq}\)中二分找到解
具体的，维护\(a_{lq}=0,a_{rq}=1\)，若\(a_{\lfloor\frac{l+r}{2}\rfloor q}=0\)则令\(l=\lfloor\frac{l+r}{2}\rfloor+1\)，否则令\(r=\lfloor\frac{l+r}{2}\rfloor\)
另一方面，操作对序列\(\{a_{p}\}\)的影响即——
- \(+\ x\ y\)：在第\(x\)个\(0\)后加入\(y\)个\(1\)
- \(-\ x\ y\)：在第\(x\)个\(0\)前加入\(y\)个\(1\)，并删除最后的\(y\)个\(0\)
用可持久化线段树维护第\(i\)和\(i+1\)个\(0\)间\(1\)的个数，时间复杂度为\(O(n\log^{2}n)\)
#include<bits/stdc++.h>
using namespace std;
#define mid (l+r>>1)
typedef long long ll;
const int N=300005,M=N*100;
int n,V,x,y,rt[N],ls[M],rs[M],g[M];
ll z,f[M];char s[9];
int Cpy(int k){
ls[++V]=ls[k],rs[V]=rs[k],g[V]=g[k],f[V]=f[k];
return V;
}
void up(int k,int l){
g[k]=(f[rs[k]] ? l+g[rs[k]] : g[ls[k]]);
f[k]=f[ls[k]]+f[rs[k]];
}
void update(int &k,int l,int r,int x,int y){
k=Cpy(k);
if (l==r){
g[k]=1,f[k]+=y;
return;
}
if (x<=mid)update(ls[k],l,mid,x,y);
else update(rs[k],mid+1,r,x,y);
up(k,mid-l+1);
}
void Update(int &k,int l,int r,int &x){
if (f[k]<=x){
x-=f[k],k=0;
return;
}
k=Cpy(k);
if (l==r){
f[k]-=x,g[k]=(f[k]>0),x=0;
return;
}
Update(rs[k],mid+1,r,x);
if (x)Update(ls[k],l,mid,x);
up(k,mid-l+1);
}
pair<bool,int> query(int k,int l,int r,ll x,int y=0){
if (l==r)return make_pair((x>0),l);
if ((!y)&&(!f[rs[k]]))return query(ls[k],l,mid,x);
ll s=f[ls[k]]+mid-l+1;
return (x<s ? query(ls[k],l,mid,x,1) : query(rs[k],mid+1,r,x-s,y));
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",s);
rt[i]=rt[i-1];
if (s[0]=='+'){
scanf("%d%d",&x,&y);
update(rt[i],1,1e9,x,y);
}
if (s[0]=='-'){
scanf("%d%d",&x,&y);
if (x>1)update(rt[i],1,1e9,x-1,y);
Update(rt[i],1,1e9,y);
}
if (s[0]=='R'){
scanf("%d",&x);
rt[i]=rt[i-x-1];
}
if (s[0]=='?'){
scanf("%lld",&z);
if (!f[rt[i]]){
puts("-1 -1");
continue;
}
ll l=0,r=(g[rt[i]]+f[rt[i]])/z;
while (l+1<r){
if (query(rt[i],1,1e9,mid*z).first)r=mid;
else l=mid;
}
printf("%d ",query(rt[i],1,1e9,l*z).second);
printf("%lld\n",f[rt[i]]-(r*z-query(rt[i],1,1e9,r*z).second));
}
}
return 0;
}