回滚莫队
cpp
namespace MoRollBack{
// 回滚莫队,改work
struct Node{
int id,l,r;
};
// be块编号，[L,R]块边界
vector<int> be,L,R;
// block块大小, tot块数量
int block,tot;
vector<Node> que; // 询问
vector<pair<int&,int>> his;// 回滚辅助数组
bool cmp(const Node &x,const Node &y){
return (be[x.l]^be[y.l])?be[x.l]<be[y.l]:x.r<y.r;
}
void init(int n){
block=sqrt(n);
tot=(n+block-1)/block;
be.assign(n+1,0);
L.assign(tot+1,0);
R.assign(tot+1,0);
his.clear();
que.clear();
for(int i=1;i<=tot;i++){
L[i]=block*(i-1)+1,R[i]=min(block*i,n);
for(int j=L[i];j<=R[i];j++)be[j]=i;
}
}
void add_query(int l,int r){
int id=que.size();
que.push_back({id,l,r});
}
void Set(int &x,int y){
his.push_back({x,x});
x=y;
}
void rollback(int t=0){
while(his.size()>t){
auto [x,y]=his.back();
x=y;
his.pop_back();
}
}
}
using namespace MoRollBack;
void solve(){
int n;
cin>>n;
vector<int> nums,w(n+1);
for(int i=1;i<=n;i++)cin>>w[i],nums.push_back(w[i]);
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(),nums.end()),nums.end());
for(int i=1;i<=n;i++)w[i]=lower_bound(nums.begin(),nums.end(),w[i])-nums.begin();
init(n);
int m;
cin>>m;
for(int i=0;i<m;i++){
int l,r;
cin>>l>>r;
add_query(l,r);
}
auto work=[&](){
sort(que.begin(),que.end(),cmp);
vector<int> mx(nums.size()),mn(nums.size());
vector<int> ans(que.size());
auto add=[&](int x,int &res){
if(!mx[w[x]]){
Set(mx[w[x]],x);
Set(mn[w[x]],x);
}
else{
if(x>mx[w[x]])Set(mx[w[x]],x);
if(x<mn[w[x]])Set(mn[w[x]],x);
}
if(mx[w[x]]-mn[w[x]]>res)Set(res,mx[w[x]]-mn[w[x]]);
};
for(int i=0,j;i<m;i++){
j=i;
while(j+1<m&&be[que[j].l]==be[que[j+1].l])j++;
int right=R[be[que[i].l]];
while(i<=j&&que[i].r<=right){
auto [id,ql,qr]=que[i++];
int res=0;
for(int k=ql;k<=qr;k++)add(k,res);
ans[id]=res;
rollback();
}
int res=0,l=right+1,r=right;
while(i<=j){
auto [id,ql,qr]=que[i++];
while(r<qr)add(++r,res);
int t=his.size();
while(l>ql)add(--l,res);
ans[id]=res;
l=right+1;
rollback(t);
}
rollback();
i=j;
}
return ans;
};
for(auto &x:work())cout<<x<<"\n";
}