我只负责 D、F题解。
D Serious Dedication II（终极奉献 II）
很麻烦的一道题，为了卡掉暴力搞得非常严肃。二维前缀和的题目大概以后不会出了……
访问每个位置的“菱形”情况，需要把单次访问操作的时间压下来，尽量用运算个数固定的访问方法。
本题解二维前缀和的部分可见于终极奉献 I，比赛链接。
对齐解法
通过 bfs 扩散，将输入的中心点坐标连续扩散 次就得到了已有耕地的完整耕地图。
C/C++ 代码：
#include<stdio.h>
int a[2500][2500],b1[2500][5000],b2[2500][5000];
int qx[2499*2499],qy[2499*2499],ql,qr;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int ans[1998001+1];
int main()
{
int n,k,l;scanf("%d%d%d",&n,&k,&l);
for(int i=0;i<n;i++)
{
scanf("%d%d",qx+i,qy+i);
a[qx[i]][qy[i]]=1;
}
qr=n-1;//队列有效下标闭区间[ql,qr]
for(int _=0;_<k;_++)//扩散k次
{
int tqr=qr;//标记现在qr位置
while(ql<=tqr)
{
int x=qx[ql],y=qy[ql];ql++;
for(int f=0;f<4;f++)
{
int xx=x+dx[f],yy=y+dy[f];
if(a[xx][yy]==0)
{
a[xx][yy]=1;
++qr;qx[qr]=xx;qy[qr]=yy;
}
}
}
}
for(int i=1;i<=l;i++)for(int j=1;j<=l;j++)
a[i][j]=!a[i][j]+a[i][j-1];
//一维行前缀和
for(int x=1;x<=l;x++)for(int y=1;y<=l;y++)
b1[x][y-x+l]=b2[x][x+y]=a[x][y];
//应用坐标变换
//u=x
//v=y-x+l和v=x+y
for(int i=1;i<=l;i++)for(int j=1;j<=2*l;j++)
b1[i][j]+=b1[i-1][j],b2[i][j]+=b2[i-1][j];
//一维列前缀和
for(int x0=k+1;x0+k<=l;x0++)
for(int y0=k+1;y0+k<=l;y0++)
{
int sum=0;
sum+=b1[x0][(y0+k)-x0+l]-b1[x0-k-1][(y0+k)-x0+l];
sum-=b1[x0+k][(y0-1)-(x0+k)+l]-b1[x0-1][(y0-1)-(x0+k)+l];
sum+=b2[x0+k][(x0+k)+y0]-b2[x0-1][(x0+k)+y0];
sum-=b2[x0][x0+(y0-k-1)]-b2[x0-k-1][x0+(y0-k-1)];
sum-=a[x0][y0+k]-a[x0][y0-k-1];
//当然你也可以当初加的时候就省去
//a[x0][y0+k]-a[x0][y0-k-1];这块
ans[sum]++;
}
int q;scanf("%d",&q);
while(q--)
{
int a;scanf("%d",&a);
printf("%d\n",ans[a]);
}
return 0;
}
旋转做法（不分奇偶）
考虑将菱形旋转 看看
利用坐标公式
可以将原有的“菱形”格点坐标集合化为“正方形”坐标集合。
考虑到这种变换会出现负数，给 加一个截距即可。
将原本黄色的格子旋转后得到的蓝色格子是有无相间的，根据计算可知这些蓝色格子两个坐标之和要不是奇数，要不就是偶数，处理的时候把空白位置空出来就行。
C/C++ 代码：
#include<stdio.h>
int a[5001][5001];//空间给够就是硬气
int ans[1998001+1];
int main()
{
int n,k,l;scanf("%d%d%d",&n,&k,&l);
for(int i=0;i<n;i++)
{
int x0,y0;scanf("%d%d",&x0,&y0);
int x1=x0+y0,y1=y0-x0+l;
a[x1-k][y1-k]++;
a[x1-k][y1+k+1]--;
a[x1+k+1][y1-k]--;
a[x1+k+1][y1+k+1]++;
//储存为差分的形式
}
for(int i=1;i<=2*l;i++)for(int j=1;j<=2*l;j++)
a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];
//做二维前缀和
for(int u=1;u<=2*l;u++)for(int v=1;v<=2*l;v++)
{
//u+v+l=(x+y)+(y-x+l)+l=2*(y+l) 是偶数
//只有u+v+l是偶数是有效格，奇数的格一律设置成0
if(u+v+l&1)a[u][v]=0;
else a[u][v]=!a[u][v];
//如果某有效格被遍历过1次及以上，那么记为0，否则是1
//0和1分别表示该格上的空耕地/不被包含的格子数
//显然其值只能是0或1
}
for(int i=1;i<=2*l;i++)for(int j=1;j<=2*l;j++)
a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];
//做二维前缀和，方便后面算二维切片的元素总和
for(int x=k+1;x+k<=l;x++)for(int y=k+1;y+k<=l;y++)
{
int x1=x+y,y1=y-x+l;
int res=a[x1+k][y1+k]-a[x1-k-1][y1+k]-a[x1+k][y1-k-1]+a[x1-k-1][y1-k-1];
ans[res]++;//预处理出来所有可能的方案
}
int q;scanf("%d",&q);
while(q--)
{
int a;scanf("%d",&a);
printf("%d\n",ans[a]);
}
return 0;
}
旋转解法（分奇偶，比较精致，仅供参考）
最初的想法，把空间利用到了极致，但是本题空间给得很大，不推荐这么写。
我们观察到 只能套在
外面，
只能套在
外面，遂将格点分奇偶讨论。
分奇偶旋转示意：
返回到原图中看看：
观察到：设旋转前格点的坐标为 ，那么
相同的格点在一条斜线上，
相同的格点在一条斜线上，两种斜线正交。根据我们坐标转化的经验，那么设旋转后的坐标为
，则可以有
由于我们先前分了奇偶两组（如果不分奇偶似乎也不是不可以做，这种操作似乎更“脑淤血”了），所以这种坐标也是分奇偶的，意味着相邻有意义的格点一维坐标相差 ，让它们算完再除以
即可。
我们发现这个 有可能是个负数，再加上一个截距让起始坐标
对齐后就完美了：
注意这套坐标转换公式要套两组不同的奇偶坐标。最后通过找关键格点对齐截距，当然数组开得够大，坐标也可以不从 开始。
对齐坐标后就坐标就都在 上了，非常方便我们使用二维前缀和做后续的操作。
C/C++ 代码：
#include<stdio.h>
int ec[1502][1502],oc[1502][1502];
//even coordinate & odd coordinate
//偶数坐标 和 奇数坐标 两套坐标
int ebu,ebv,obu,obv;
//even/odd (coordinates) base
//坐标变换的两套变换截距，用这个截距对齐坐标位置
//u=(x+y)/2+bu
//v=(y-x)/2+bv
//分出来两套坐标截距的做法比较精致，也可以不这么做
int ans[2002001+1];
int isodd(int x,int y){return (x+y)&1;}
int d(int x){return (x-(x&1))/2;}//d是⌊x/2⌋函数
//C/C++ 的整数除法是向零取整
//但是此处我们要求严格向下取整
void add(int x,int y,int val)
{
if(isodd(x,y))oc[d(x+y)+obu][d(y-x)+obv]+=val;
else ec[d(x+y)+ebu][d(y-x)+ebv]+=val;
}
int query(int x,int y)
{
if(isodd(x,y))return oc[d(x+y)+obu][d(y-x)+obv];
else return ec[d(x+y)+ebu][d(y-x)+ebv];
}
int main()
{
int n,k,l;scanf("%d%d%d",&n,&k,&l);
//用 (1,k+1)/(2,k+1) 确定两套新坐标下的第一行 ⌊(x+y)/2⌋=1
if(isodd(1,k+1))obu=1-d(1+(k+1)),ebu=1-d(2+(k+1));
else ebu=1-d(1+(k+1)),obu=1-d(2+(k+1));
//用 (l-k,1)/(l-k,2) 确定两套新坐标下的第一列 ⌊(y-x)/2⌋=1
if(isodd(l-k,1))obv=1-d(1-(l-k)),ebv=1-d(2-(l-k));
else ebv=1-d(1-(l-k)),obv=1-d(2-(l-k));
for(int i=0;i<n;i++)
{
int x0,y0;scanf("%d%d",&x0,&y0);
add(x0,y0-k,1);add(x0+k+1,y0+1,-1);
add(x0-k-1,y0+1,-1);add(x0,y0+k+2,1);
add(x0,y0-k+1,1);add(x0+k,y0+1,-1);
add(x0-k,y0+1,-1);add(x0,y0+k+1,1);
//储存为差分的形式
}
for(int i=1;i<=l-k;i++)for(int j=1;j<=l-k;j++)
{
ec[i][j]+=ec[i-1][j]+ec[i][j-1]-ec[i-1][j-1];
oc[i][j]+=oc[i-1][j]+oc[i][j-1]-oc[i-1][j-1];
//做二维前缀和
}
for(int i=1;i<=l-k;i++)for(int j=1;j<=l-k;j++)
{
ec[i][j]=!(ec[i][j]);
oc[i][j]=!(oc[i][j]);
//如果某格被遍历过1次及以上，那么记为0，否则是1
//0和1分别表示该格上的空耕地/不被包含的格子数
//显然其值只能是0或1
}
for(int i=1;i<=l-k;i++)for(int j=1;j<=l-k;j++)
{
ec[i][j]+=ec[i-1][j]+ec[i][j-1]-ec[i-1][j-1];
oc[i][j]+=oc[i-1][j]+oc[i][j-1]-oc[i-1][j-1];
//做二维前缀和，方便后面算二维切片的元素总和
}
for(int i=k+1;i<=l-k;i++)for(int j=k+1;j<=l-k;j++)
{
int res=0;
res+=query(i,j+k)-query(i+k+1,j-1)-query(i-k-1,j-1)+query(i,j-k-2);
res+=query(i,j+k-1)-query(i+k,j-1)-query(i-k,j-1)+query(i,j-k-1);
ans[res]++;
//预处理出来所有可能的方案
}
int q;scanf("%d",&q);
for(int i=0;i<q;i++)
{
int a;scanf("%d",&a);
printf("%d\n",ans[a]);
}
return 0;
}
F Rheanna's General List
数据结构题，考虑好硬上就行，细节有点多，有多种方法：
线段树
线段树维护，记录深度信息。
一棵线段树 s1 维护区间最小值和最小值的个数，顺便适用树上结点表示的段的最小值为 的最小值数量求得最外层表上的位置信息；另一个线段树
s2 维护区间最大值即可。
为什么要分两个树？因为 MERGE 时，一个树不能既让表首深度保持 1，又体现出来表首的深度加一了。
MERGE 只需要给 s1 [L+1,R] 数值加一，给 s2 [L,R] 数值加一。
然后记录每次修改的区间跨度，需要明白如果 R 位置上是一个表首位置，还需要把这个表的尾部找到，将信息记录到最左边的位置（新表首），入栈记录即可。
SPLIT 根据记录的栈信息得到修改的区间跨度，需要给 s1 [L+1,R] 数值减一，给 s2 [L,R] 数值减一。
QUERY_LENGTH 只需要输出 s1 最小值为 的最小值数量。
QUERY_DEPTH 只需要输出 s2 的最大值即可。
C++ 代码：
#include<stack>
#include<string>
#include<vector>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
class Segment_Tree_Method
{
struct node{int max_val,min_val,min_cnt,tag;};
struct Segment_Tree
{
vector<node> x;
#define mid (l+r>>1)
#define ls (2*p)
#define rs (2*p+1)
void pushup(int p)
{
if(x[ls].min_val==x[rs].min_val)
{
x[p].min_val=x[ls].min_val;
x[p].min_cnt=x[ls].min_cnt+x[rs].min_cnt;
}
else
{
int min_son=x[ls].min_val<x[rs].min_val?ls:rs;
x[p].min_val=x[min_son].min_val;
x[p].min_cnt=x[min_son].min_cnt;
}
x[p].max_val=max(x[ls].max_val,x[rs].max_val);
}
void modify_node(int p,int val)
{
x[p].min_val+=val;
x[p].max_val+=val;
x[p].tag+=val;
}
void pushdown(int p)
{
if(x[p].tag!=0)
{
modify_node(ls,x[p].tag);
modify_node(rs,x[p].tag);
x[p].tag=0;
}
}
void build(int p,int l,int r)
{
if(l==r)return x[p]={1,1,1,0},void();
build(ls,l,mid);
build(rs,mid+1,r);
pushup(p);
}
void add(int p,int l,int r,int L,int R,int V)
{
if(L<=l&&r<=R)
{
modify_node(p,V);
return;
}
pushdown(p);
if(L<=mid)add(ls,l,mid,L,R,V);
if(R>mid)add(rs,mid+1,r,L,R,V);
pushup(p);
}
int Kth_pos_min_eq1(int p,int l,int r,int K)
{
if(l==r)return l;
pushdown(p);
int ls_cnt=(x[ls].min_val==1)*x[ls].min_cnt;
if(K<=ls_cnt)return Kth_pos_min_eq1(ls,l,mid,K);
else return Kth_pos_min_eq1(rs,mid+1,r,K-ls_cnt);
}
#undef mid
#undef ls
#undef rs
};
Segment_Tree s1,s2;
vector<stack<int,vector<int>>> right_pos;
int n;
/*
std::stack<int> 的默认底层容器是 std::deque<int>，
而单个 std::deque<int> 只有一个元素也要占用不小的空间，
详见 https://zh.cppreference.com/w/cpp/container/deque
所以，如果同时在多个 std::deque<int> 加入元素会使用一大堆空间，
好在本题空间较大，此处使用默认底层容器 std::deque<int> 也并无大碍。
std::stack<int,std::vector<int>>意味底层容器是 std::vector<int>，
后者空间使用量明显小于前者。
*/
public:
void init(int _n,int m)
{
n=_n;
s1.x.resize(4*n);s1.build(1,1,n);
s2.x.resize(4*n);s2.build(1,1,n);
right_pos.resize(n+1);
}
int query_length(){return (s1.x[1].min_val==1)*s1.x[1].min_cnt;}
int query_depth(){return s2.x[1].max_val;}
void merge(int l,int r)
{
int L=s1.Kth_pos_min_eq1(1,1,n,l);
int R=s1.Kth_pos_min_eq1(1,1,n,r);
if(!right_pos[R].empty())R=right_pos[R].top();//连续覆盖
right_pos[L].push(R);
if(L<R)s1.add(1,1,n,L+1,R,1);
s2.add(1,1,n,L,R,1);
}
void split(int pos)
{
int L=s1.Kth_pos_min_eq1(1,1,n,pos);
if(right_pos[L].empty())return;
int R=right_pos[L].top();right_pos[L].pop();
if(L<R)s1.add(1,1,n,L+1,R,-1);
s2.add(1,1,n,L,R,-1);
}
// private:void print(int p)
// {
// }
// public:void print()
// {
// cout<<"@"<<query_length()<<' '<<query_depth()<<endl;
// }
};
Segment_Tree_Method L;
int main()
{
cin.tie(0)->sync_with_stdio(0);
int n,m;cin>>n>>m;
L.init(n,m);
// L.print();
while(m--)
{
string s;cin>>s;
if(s[0]=='M')
{
int l,r;cin>>l>>r;
L.merge(l,r);
}
else if(s[0]=='S')
{
int x;cin>>x;
L.split(x);
}
else if(s[0]=='Q')
{
// cout<<"@"<<s<<' '<<m<<' ';
if(s[6]=='L')cout<<L.query_length()<<'\n';
else if(s[6]=='D')cout<<L.query_depth()<<'\n';
}
// L.print();
}
return 0;
}
Treap
维护查询位次、分裂、合并操作。
每次 MERGE 操作把对应一块劈出来，新建一个结点来表示子表，SPLIT 操作再把找到的子表主体并回去。
C++ 代码：
#include<string>
#include<vector>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{int dat,ls,rs,vs,size,dep;};
//dat：优先程度标记，此处没有用随机赋值的方式
//ls：左子结点编号
//rs：右子结点编号
//vs：虚子结点编号，用于记录寄存在该位置上的子表
//size：子树结点数
//dep：子树上的全体子表/元素深度，元素深度为1
class Treap
{
vector<node> x;int root;
void pushup(int p)
{
x[p].dep=max({x[x[p].ls].dep,x[x[p].rs].dep,x[x[p].vs].dep+1});
x[p].size=x[x[p].ls].size+x[x[p].rs].size+1;
}
int build(int l,int r,int d)
{
int mid=l+r>>1;
x[mid].dat=d;
if(l<=mid-1)x[mid].ls=build(l,mid-1,d+1);
if(mid+1<=r)x[mid].rs=build(mid+1,r,d+1);
return pushup(mid),mid;
}
void _split(int p,int k,int&t1,int&t2)
{
//分成[1,k]和[k+1,total size]两部分
if(p==0)return t1=t2=0,void();
if(x[x[p].ls].size+1>k)t2=p,_split(x[p].ls,k,t1,x[p].ls);
else t1=p,_split(x[p].rs,k-(x[x[p].ls].size+1),x[p].rs,t2);
pushup(p);
}
int _merge(const int t1,const int t2)
{
if(t1==0||t2==0)return t1|t2;
if(x[t1].dat<x[t2].dat)//dat 小根
{
x[t1].rs=_merge(x[t1].rs,t2);
return pushup(t1),t1;
}
else
{
x[t2].ls=_merge(t1,x[t2].ls);
return pushup(t2),t2;
}
}
int new_node(int sr)//subtree_root
{
x.push_back({x[sr].dat,0,0,sr,1,x[sr].dep+1});
return x.size()-1;
}
vector<int> find_kth_path(int now,int k)
{
vector<int>path={now};
while(now)
{
if(k<=x[x[now].ls].size)now=x[now].ls;
else
{
k-=x[x[now].ls].size+1;
if(k==0)break;
now=x[now].rs;
}
path.push_back(now);
}
return path;
}
public:
void init(int n,int m)
{
x.reserve(n+m+1);x.resize(n+1);
root=build(1,n,0);
}
int query_length(){return x[root].size;}
int query_depth(){return x[root].dep;}
void merge(int l,int r)
{
assert(r<=query_length());
int t1,t2,t3;
_split(root,r,t2,t3);
_split(t2,l-1,t1,t2);
root=_merge(_merge(t1,new_node(t2)),t3);
}
void split(int pos)
{
assert(pos<=query_length());
vector<int>&&path=find_kth_path(root,pos);
int p=path.back();
if(x[p].vs!=0)
{
int vs=x[p].vs;
swap(x[p],x[x[p].vs]);
x[p].ls=_merge(x[vs].ls,x[p].ls);
x[p].rs=_merge(x[p].rs,x[vs].rs);
for(int i=path.size()-1;i>=0;i--)pushup(path[i]);
}
}
// private:void print(int p)
// {
// if(p==0)return;
// print(x[p].ls);
// if(x[p].vs)cout<<'(',print(x[p].vs),cout<<')';
// else cout<<'*';
// print(x[p].rs);
// }
// public:void print()
// {
// cout<<"(";
// print(root);
// cout<<")"<<endl;
// }
};
Treap L;
int main()
{
cin.tie(0)->sync_with_stdio(0);
int n,m;cin>>n>>m;
L.init(n,m);
// L.print();
while(m--)
{
string s;cin>>s;
if(s[0]=='M')
{
int l,r;cin>>l>>r;
L.merge(l,r);
}
else if(s[0]=='S')
{
int x;cin>>x;
L.split(x);
}
else if(s[0]=='Q')
{
if(s[6]=='L')cout<<L.query_length()<<'\n';
else if(s[6]=='D')cout<<L.query_depth()<<'\n';
}
// L.print();
}
return 0;
}
Splay
均摊近似线性方法。
#include<string>
#include<vector>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{union{int son[2];struct{int ls,rs;};};int fa,vs,size,dep;};
//size：子树结点数
//ls/son[0]：左子结点编号
//rs/son[1]：右子结点编号
//fa：父结点编号
//vs：虚子结点编号，用于记录寄存在该位置上的子表
//dep：子树上的全体子表/元素深度，元素深度为1
class SplayTree
{
vector<node> x;int root;
void pushup(int p)
{
x[p].dep=max({x[x[p].ls].dep,x[x[p].rs].dep,x[x[p].vs].dep+1});
x[p].size=x[x[p].ls].size+x[x[p].rs].size+1;
}
int build(int l,int r)
{
int mid=l+r>>1;
if(l<=mid-1)x[x[mid].ls=build(l,mid-1)].fa=mid;
if(mid+1<=r)x[x[mid].rs=build(mid+1,r)].fa=mid;
return pushup(mid),mid;
}
int new_node(int sr)//subtree_root
{
x.push_back({{0,0},x[sr].fa,sr,1,x[sr].dep+1});
return static_cast<int>(x.size())-1;
}
#define get(xx) (xx==x[x[xx].fa].rs)
void rotate(int p)
{
int f=x[p].fa;bool ws=get(p);
if(x[f].fa)x[x[f].fa].son[get(f)]=p;x[p].fa=x[f].fa;
x[x[f].son[ws]=x[p].son[!ws]].fa=f;
x[x[p].son[!ws]=f].fa=p;
pushup(f),pushup(p);
}
void splay(int p,int target=0)
{
for(int f;(f=x[p].fa)!=target;rotate(p))
if(x[f].fa!=target)rotate(get(p)==get(f)?f:p);
if(target==0)root=p;
}
int kth(int k)
{
int now=root;
while(now)
{
if(k<=x[x[now].ls].size)now=x[now].ls;
else
{
k-=x[x[now].ls].size+1;
if(k==0)break;
now=x[now].rs;
}
}
return now;
}//询问完kth后续要splay求出的结点
public:
void init(int n,int m)
{
x.reserve(n+m+1+2);x.resize(n+1+2);
root=build(1,n+2);
}
int query_length(){return x[root].size-2;}
int query_depth(){return x[root].dep;}
void merge(int l,int r)
{
assert(r<=query_length());
l++;r++;
int nl=kth(l-1);splay(nl);
int nr=kth(r+1);splay(nr,nl);
splay(x[nr].ls=new_node(x[nr].ls));
}
void split(int pos)
{
assert(pos<=query_length());
pos++;
int nl=kth(pos-1);splay(nl);
int nr=kth(pos+1);splay(nr,nl);
int p=x[nr].ls;
if(x[p].vs!=0)
x[x[nr].ls=x[p].vs].fa=nr,
splay(x[nr].ls);
}
// private:void print(int p)
// {
// if(p==0)return;
// print(x[p].ls);
// if(x[p].vs)cout<<'(',print(x[p].vs),cout<<')';
// else cout<<'*';
// print(x[p].rs);
// }
// public:void print()
// {
// cout<<"(";
// print(root);
// cout<<")"<<endl;
// }
};
SplayTree L;
int main()
{
cin.tie(0)->sync_with_stdio(0);
int n,m;cin>>n>>m;
L.init(n,m);
// L.print();
while(m--)
{
string s;cin>>s;
if(s[0]=='M')
{
int l,r;cin>>l>>r;
L.merge(l,r);
}
else if(s[0]=='S')
{
int x;cin>>x;
L.split(x);
}
else if(s[0]=='Q')
{
if(s[6]=='L')cout<<L.query_length()<<'\n';
else if(s[6]=='D')cout<<L.query_depth()<<'\n';
}
// L.print();
}
return 0;
}
两种分块方法
记录 上的深度，
上深度为
的位置等。
维护查询位次、区间加、区间减等操作。注意不要写假了。
MERGE 给对应区间深度加上 ，这里可以考虑在不更改头的位置的深度用来保证位次查询正确，以此可以分出来两种做法，见下面代码。
SPLIT 找到之前 MERGE 的时候的区间，深度减 ，同时维护深度加减和深度为
可能会写假，所以细节比较多。
C++ 代码（其一）：
#include<cmath>
#include<stack>
#include<string>
#include<vector>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
class Blocks
{
int Bs,Brs,num;//Block size,Brink size
vector<vector<int>> depth[2],Bdepth_rec[2];
vector<int> Bdepth_base;
vector<stack<int,vector<int>>> right_pos;
/*
std::stack<int> 的默认底层容器是 std::deque<int>，
而单个 std::deque<int> 只有一个元素也要占用不小的空间，
详见 https://zh.cppreference.com/w/cpp/container/deque
所以，如果同时在多个 std::deque<int> 加入元素会使用一大堆空间，
好在本题空间较大，此处使用默认底层容器 std::deque<int> 也并无大碍。
std::stack<int,std::vector<int>>意味底层容器是 std::vector<int>，
后者空间使用量明显小于前者。
*/
void depth_add(int a,int i,int j)
{
int&t=depth[a][i][j];
if(t+1==Bdepth_rec[a][i].size())
Bdepth_rec[a][i].push_back(0);
Bdepth_rec[a][i][t]--;
Bdepth_rec[a][i][++t]++;
}
bool depth_eq1(int i,int j)const
{
return Bdepth_base[i]+depth[1][i][j]==1;
}
int Bdepth_eq1(int i)const
{
if(Bdepth_base[i]>1)return 0;
else return Bdepth_rec[1][i][1-Bdepth_base[i]];
}
int Bsize(int i)const{return i==num-1?Brs:Bs;}
pair<int,int> kth(int k)//序数从0开始
{
int i=0,j=0;
for(;i<num;i++)
{
int t=Bdepth_eq1(i);
if(k>=t)k-=t;else break;
}
for(;j<Bsize(i);j++)
{
if(depth_eq1(i,j))
{
if(k==0)break;
else k--;
}
}
return{i,j};
}
public:
void init(int n,int m)
{
Bs=ceil(sqrt(n));//简简单***方根分块，不一定最佳，但够用
if(n%Bs==0)Brs=Bs;else Brs=n%Bs;
num=(n+Bs-1)/Bs;//上取整
for(int a=0;a<=1;a++)
{
depth[a].resize(num);
for(int i=0;i<num-1;i++)depth[a][i].resize(Bs);
depth[a].back().resize(Brs);
}
for(int a=0;a<=1;a++)
{
Bdepth_rec[a].resize(num);
for(int i=0;i<num-1;i++)Bdepth_rec[a][i]={Bs};
Bdepth_rec[a].back()={Brs};
}
Bdepth_base.resize(num,1);
right_pos.resize(n);
}
void merge(int l,int r)
{
l--;r--;//下标从0开始
auto[L,I]=kth(l);
auto[R,J]=kth(r);
if(right_pos[R*Bs+J].size())
{
auto[R1,J1]=div(right_pos[R*Bs+J].top(),Bs);
R=R1;J=J1;
}
right_pos[L*Bs+I].push(R*Bs+J);
if(L==R)
{
for(int a=0;a<=1;a++)
{
for(int i=I+a;i<=J;i++)depth_add(a,L,i);
}
}
else
{
for(int i=L+1;i<R;i++)Bdepth_base[i]++;
for(int a=0;a<=1;a++)
{
for(int i=I+a;i<Bs;i++)depth_add(a,L,i);
for(int i=0;i<=J;i++)depth_add(a,R,i);
}
}
}
void split(int pos)
{
pos--;//下标从0开始
auto[L,I]=kth(pos);
auto&st=right_pos[L*Bs+I];
if(st.size())
{
int r=st.top();st.pop();
auto[R,J]=div(r,Bs);
if(L==R)
{
Bdepth_base[L]--;
for(int a=0;a<=1;a++)
{
for(int i=0;i<I+a;i++)depth_add(a,L,i);
for(int i=J+1;i<Bsize(L);i++)depth_add(a,L,i);
}
}
else
{
Bdepth_base[L]--;
for(int i=L+1;i<R;i++)Bdepth_base[i]--;
Bdepth_base[R]--;
for(int a=0;a<=1;a++)
{
for(int i=0;i<I+a;i++)depth_add(a,L,i);
for(int i=J+1;i<Bsize(R);i++)depth_add(a,R,i);
}
}
}
}
int query_length()
{
int length=0;
for(int i=0;i<num;i++)length+=Bdepth_eq1(i);
return length;
}
int query_depth()
{
int maxdepth=0;
for(int i=0;i<num;i++)
maxdepth=max(maxdepth,
int(Bdepth_base[i]+Bdepth_rec[0][i].size()-1));
return maxdepth;
}
// void print()
// {
// cout<<"@"<<query_length()<<endl;
// for(int i=0;i<num;i++)
// for(int j=0;j<Bsize(i);j++)
// cout<<Bdepth_base[i]+depth[0][i][j]<<' ';
// cout<<endl;
// for(int i=0;i<num;i++)
// for(int j=0;j<Bsize(i);j++)
// cout<<Bdepth_base[i]+depth[1][i][j]<<' ';
// cout<<endl;
// }
};
Blocks L;
int main()
{
cin.tie(0)->sync_with_stdio(0);
int n,m;cin>>n>>m;
L.init(n,m);
// L.print();
while(m--)
{
static int cnt=0;
string s;cin>>s;
if(s[0]=='M')
{
int l,r;cin>>l>>r;
L.merge(l,r);
}
else if(s[0]=='S')
{
int x;cin>>x;
L.split(x);
}
else if(s[0]=='Q')
{
if(s[6]=='L')cout<<L.query_length()<<'\n';
else if(s[6]=='D')cout<<L.query_depth()<<'\n';
}
// L.print();
}
return 0;
}
C++ 代码（其二）：
#include<set>
#include<cmath>
#include<stack>
#include<string>
#include<vector>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;
using pii=pair<int,int>;
class Blocks
{
int Bs,Brs,num;//Block size,Brink size
vector<vector<int>> depth,Bdepth_rec;
vector<int> Bdepth_base;
vector<stack<pii,vector<pii>>> list_info;
vector<multiset<int>> Bdepthes;
void depth_add(int i,int j)
{
int&t=depth[i][j];
if(t+1==Bdepth_rec[i].size())
Bdepth_rec[i].push_back(0);
Bdepth_rec[i][t]--;
Bdepth_rec[i][++t]++;
}
bool depth_eq1(int i,int j)const
{
return Bdepth_base[i]+depth[i][j]==1;
}
int Bdepth_eq1(int i)const
{
if(Bdepth_base[i]>1)return 0;
else return Bdepth_rec[i][1-Bdepth_base[i]];
}
int get_maxdepth(int i,int j)const
{
if(list_info[i*Bs+j].size())
return list_info[i*Bs+j].top().second;
return 1;
}
int get_Bmaxdepth(int i)
{
return *--Bdepthes[i].end();
}
int Bsize(int i)const{return i==num-1?Brs:Bs;}
pair<int,int> kth(int k)//0-indexed
{
int i=0,j=0;
for(;i<num;i++)
{
int t=Bdepth_eq1(i);
if(k>=t)k-=t;else break;
}
for(;j<Bsize(i);j++)
{
if(depth_eq1(i,j))
{
if(k==0)break;
else k--;
}
}
return{i,j};
}
public:
void init(int n,int m)
{
Bs=ceil(sqrt(n));
if(n%Bs==0)Brs=Bs;else Brs=n%Bs;
num=(n+Bs-1)/Bs;//上取整
//
depth.resize(num);
for(int i=0;i<num-1;i++)depth[i].resize(Bs);
depth.back().resize(Brs);
//
Bdepth_rec.resize(num);
for(int i=0;i<num-1;i++)Bdepth_rec[i]={Bs};
Bdepth_rec.back()={Brs};
//
Bdepth_base.resize(num,1);
//
list_info.resize(n);
//
Bdepthes.resize(num);
for(int i=0;i<num;i++)Bdepthes[i].insert(1);
}
void merge(int l,int r)
{
l--;r--;
auto[L,I]=kth(l);//cout<<"1$ "<<L<<" "<<I<<endl;
auto[R,J]=kth(r);//cout<<"2$ "<<R<<" "<<J<<endl;
if(list_info[R*Bs+J].size())
{
auto[R1,J1]=div(list_info[R*Bs+J].top().first,Bs);
R=R1;J=J1;
}
int maxdepth=get_maxdepth(L,I);
if(L==R)
{
for(int i=I+1;i<=J;i++)
{
depth_add(L,i);
maxdepth=max(maxdepth,get_maxdepth(L,i));
}
}
else
{
for(int i=I+1;i<Bs;i++)
{
depth_add(L,i);
maxdepth=max(maxdepth,get_maxdepth(L,i));
}
for(int i=L+1;i<R;i++)
{
Bdepth_base[i]++;
maxdepth=max(maxdepth,get_Bmaxdepth(i));
}
for(int i=0;i<=J;i++)
{
depth_add(R,i);
maxdepth=max(maxdepth,get_maxdepth(R,i));
}
}
Bdepthes[L].insert(maxdepth+1);
list_info[L*Bs+I].emplace(R*Bs+J,maxdepth+1);
}
void split(int pos)
{
pos--;
auto[L,I]=kth(pos);
auto&st=list_info[L*Bs+I];
if(st.size())
{
auto[r,t_depth]=st.top();st.pop();
Bdepthes[L].erase(Bdepthes[L].lower_bound(t_depth));
auto[R,J]=div(r,Bs);
if(L==R)
{
Bdepth_base[L]--;
for(int i=0;i<=I;i++)depth_add(L,i);
for(int i=J+1;i<Bsize(L);i++)depth_add(L,i);
}
else
{
Bdepth_base[L]--;for(int i=0;i<=I;i++)depth_add(L,i);
for(int i=L+1;i<R;i++)Bdepth_base[i]--;
Bdepth_base[R]--;for(int i=J+1;i<Bsize(R);i++)depth_add(R,i);
}
}
}
int query_length()
{
int length=0;
for(int i=0;i<num;i++)length+=Bdepth_eq1(i);
return length;
}
int query_depth()
{
int maxdepth=0;
for(int i=0;i<num;i++)
maxdepth=max(maxdepth,get_Bmaxdepth(i));
return maxdepth;
}
// void print()
// {
// cout<<"@"<<query_length()<<endl;
// for(int i=0;i<num;i++)
// for(int j=0;j<Bsize(i);j++)
// cout<<Bdepth_base[i]+depth[i][j]<<' ';
// cout<<endl;
// }
};
Blocks L;
int main()
{
cin.tie(0)->sync_with_stdio(0);
int n,m;cin>>n>>m;
L.init(n,m);
// L.print();
while(m--)
{
static int cnt=0;
string s;cin>>s;
if(s[0]=='M')
{
int l,r;cin>>l>>r;
L.merge(l,r);
}
else if(s[0]=='S')
{
int x;cin>>x;
L.split(x);
}
else if(s[0]=='Q')
{
if(s[6]=='L')cout<<L.query_length()<<'\n';
else if(s[6]=='D')cout<<L.query_depth()<<'\n';
}
// L.print();
}
return 0;
}
__gnu_cxx::rope 做法
注：__gnu_cxx::rope 是 GNU 的扩展库容器，它不是 PBDS（PBDS 对应的命空间是 __gnu_pbds），不是标准库内容，更不是 STL。__gnu_cxx::rope 是一个比较复杂的（复杂到有一些不好找和改的 BUG）容器，不太好归到哪种数据结构分类中。
代码是从好兄弟那里拿来的，空间用得非常极限，懂 __gnu_cxx::rope 还是很容易想的。区间查询/修改用了线段树。
#include<bits/stdc++.h>
#include<ext/rope>
#define int long long
//define覆盖关键字是比较邪门的写法，请尽量用 typedef 或 using 套一个合适标识符代替
using namespace std;
using namespace __gnu_cxx;
const int N = 4e5+10;
const int maxn=4e5+10;
stack<pair<int,int>>sc[N];
int q, n, k, l, r, x, y, ne[N], b[N];
stack<pair<int,int>>pre[N];
rope<int> S[N];
int ans1, ans2;
long long lowbit(long long x) {
return (-x)&x;
}
struct node{
long long sum,add,mul;
int l,r;
bool flag;
}tr[4*maxn];
vector<long long>a(maxn);
int op,cnt;
void pushup(int x){
tr[x].sum=max(tr[x*2].sum,tr[x*2+1].sum);
}
void eval(int x,long long add){
tr[x].sum+=add;
}
void pushdown(int x){
eval(x*2,tr[x].add);
eval(x*2+1,tr[x].add);
tr[x*2].add+=tr[x].add;
tr[x*2+1].add+=tr[x].add;
tr[x].add=0;
}
void build(int x,int l,int r){
tr[x].l=l,tr[x].r=r;
tr[x].flag=0,tr[x].add=0;
if(l==r){
tr[x].sum=a[l];
return;
}
int mid=(l+r)/2;
build(x*2,l,mid);
build(x*2+1,mid+1,r);
pushup(x);
}
long long query(int x,int l,int r){
if(tr[x].l>=l&&tr[x].r<=r)return tr[x].sum;
pushdown(x);
int mid=(tr[x].l+tr[x].r)/2;
long long sum=-1e18;
if(l<=mid)sum=max(sum,query(x*2,l,r));
if(r>mid)sum=max(query(x*2+1,l,r),sum);
pushup(x);
return sum;
}
void update(int now,int l,int r,long long add){
if(l<=tr[now].l&&r>=tr[now].r){
tr[now].add+=add;
eval(now,add);
}
else {
pushdown(now);
int mid=(tr[now].l+tr[now].r)/2;
if(l<=mid)update(now*2,l,r,add);
if(r>mid)update(now*2+1,l,r,add);
pushup(now);
}
}
void solve(){
cnt = 0;
cin >> n >> q;
ans1 = n;
for(int i = 0; i <= n; i++){
a[i] = 1;
S[0].push_back(i);
}
build(1,1,n);
string op;
for(int i = 1; i <= q; i++){
cin >> op;
if(op == "MERGE"){
S[cnt + 1] = S[cnt];
cnt++;
cin >> x >> y;
int xx = S[cnt][x], yy = S[cnt][y];
if(sc[yy].size() > 0) yy = sc[yy].top().second;
ans1 -= y - x;
sc[xx].push({y - x, yy});
update(1,xx,yy,1);
S[cnt].erase(x + 1, y - x);
pre[xx].push({cnt - 1, x});
}
if(op == "SPLIT"){
cin >> x;
int xx = S[cnt][x];
if(sc[xx].size() == 0) continue;
S[cnt + 1] = S[cnt];
cnt++;
int z = sc[xx].top().first, yy = sc[xx].top().second;
sc[xx].pop();
ans1 += z;
update(1,xx,yy,-1);
S[cnt].insert(x + 1,S[pre[xx].top().first].substr(pre[xx].top().second + 1, z));
pre[xx].pop();
}
if(op == "QUERY_LENGTH"){
cout << ans1 << '\n';
}
if(op == "QUERY_DEPTH"){
cout << query(1,1,n) << '\n';
}
}
}
signed main(){
//freopen("output.txt", "r", stdin);
//freopen("std.txt", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--){
solve();
}
return 0;
}
其他做法
待补充……
京公网安备 11010502036488号