• 周六. 4月 20th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签
python

NOI2021 题解

由admin

11月 28, 2021

无 d2t3 。

Day 1

Edge

我们先做 ( ext{T1})​ 吧。

感觉这题很多神仙应该可以直接秒的。

感觉这道题给我一种 ( ext{LCT})​ 的感觉，我们考虑 ( ext{LCT}) 的操作。

如果考虑操作一是 ( ext{LCT}) 直接做的话，操作二能否用数据结构来维护。

我们考虑 (Access) 操作，每次就是断开一个点。

( ext{LCT}) 不行！！！！

我们可以考虑染色的，一条边两端点都是同一颜色才做贡献。

然后，就很简单了，随便维护一下就好。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
struct Data{int L,R,cnt;};
Data operator + (Data a,Data b){
	Data res;res.L=a.L,res.R=b.R;
	res.cnt=a.cnt+b.cnt+(a.R==b.L);
	return res;
}
Data cover(int x,int len){
	return (Data){x,x,len-1};
}
struct Seg_Tree1{
	struct Node{
		Data data;int tag;
	}tr[N<<2];
	void up(int u){
		tr[u].data=tr[u<<1].data+tr[u<<1|1].data;
	}
	void update(int u,int l,int r,int z){
		if(!z) return ;
		tr[u].data=cover(z,r-l+1),tr[u].tag=z;
	}
	void down(int u,int l,int r){
		int mid=(l+r)>>1;
		update(u<<1,l,mid,tr[u].tag);
		update(u<<1|1,mid+1,r,tr[u].tag);
		tr[u].tag=0;
	}
	void build(int u,int l,int r){
		tr[u].tag=0;
		if(l==r) return update(u,l,r,-l);
		int mid=(l+r)>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);
		return up(u);
	}
	void modify(int u,int l,int r,int x,int y,int z){
		if(x<=l&&r<=y) return update(u,l,r,z);
		int mid=(l+r)>>1;down(u,l,r);
		if(x<=mid) modify(u<<1,l,mid,x,y,z);
		if(y>mid) modify(u<<1|1,mid+1,r,x,y,z);
		return up(u);
	}
	Data query(int u,int l,int r,int x,int y){
		if(x<=l&&r<=y) return tr[u].data;
		int mid=(l+r)>>1;Data res1,res2;down(u,l,r);
		if(x<=mid) res1=query(u<<1,l,mid,x,y);
		if(y>mid) res2=query(u<<1|1,mid+1,r,x,y);
		if(x<=mid&&y>mid) return res1+res2;
		return x<=mid?res1:res2;
	}
}t;
struct Edge{int nxt,to;}e[N<<1];int fir[N];
void add(int u,int v,int i){e[i]=(Edge){fir[u],v},fir[u]=i;}
struct Node{int fa,son,size,dep,top,mp;}tr[N];
int dfn[N],cnt_dfn=0;
void dfs1(int u){
	tr[u].size=1,tr[u].top=u,tr[u].dep=tr[tr[u].fa].dep+1;
	for(int i=fir[u];i;i=e[i].nxt){
		if(e[i].to==tr[u].fa) continue;
		tr[e[i].to].fa=u,dfs1(e[i].to),tr[u].size+=tr[e[i].to].size;
		if(tr[e[i].to].size>tr[tr[u].son].size) tr[u].son=e[i].to;
	}
}
void dfs2(int u){
	dfn[++cnt_dfn]=u,tr[u].mp=cnt_dfn;
	if(tr[u].son) tr[tr[u].son].top=tr[u].top,dfs2(tr[u].son);
	for(int i=fir[u];i;i=e[i].nxt) if(e[i].to!=tr[u].fa&&e[i].to!=tr[u].son) dfs2(e[i].to);
}
void work(int u,int v,int z){
	while(tr[u].top!=tr[v].top){
		if(tr[tr[u].top].dep<tr[tr[v].top].dep) swap(u,v);
		t.modify(1,1,n,tr[tr[u].top].mp,tr[u].mp,z),u=tr[tr[u].top].fa;
	}
	if(tr[u].dep>tr[v].dep) swap(u,v);
	t.modify(1,1,n,tr[u].mp,tr[v].mp,z);
}
int query(int u,int v){
	int res=0,lst[2]={0,0},tag=0;
	while(tr[u].top!=tr[v].top){
		if(tr[tr[u].top].dep<tr[tr[v].top].dep) swap(u,v),tag^=1;
		Data tmp=t.query(1,1,n,tr[tr[u].top].mp,tr[u].mp);
		res+=tmp.cnt+(lst[tag]==tmp.R),lst[tag]=tmp.L,u=tr[tr[u].top].fa;
	}
	if(tr[u].dep>tr[v].dep) swap(u,v),tag^=1;
	Data tmp=t.query(1,1,n,tr[u].mp,tr[v].mp);
	res+=tmp.cnt+(lst[tag]==tmp.L)+(lst[tag^1]==tmp.R);
	return res;
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;++i) tr[i].son=fir[i]=0;
	for(int i=1;i<n;++i){
		int u,v;scanf("%d%d",&u,&v);
		add(u,v,i<<1),add(v,u,i<<1|1);
	}
	cnt_dfn=0,dfs1(1),dfs2(1),t.build(1,1,n);
	for(int i=1;i<=m;++i){
		int opt,u,v;scanf("%d%d%d",&opt,&u,&v);
		if(opt==1) work(u,v,i);
		else printf("%d
",query(u,v));
	}
	return ;
}
int main(){
	// freopen("edge2.in","r",stdin);
	// freopen("edge.out","w",stdout);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}

xpath

我们考虑每一层的选择是可以分成两个可以独立计算的部分来考虑的。

首先是选择 (n_1) 个点，这个必然一个组合数就行了。

然后考虑每一层的选择方法，感觉就是一个逆序对个数，然后关于逆序对个数的奇偶考虑，很容易想到行列式。

对于单层的，这样搞就行了，但是对于多层的，我们好像不能直接搞。

艹，我发现我读错题了。

这个题目描述好屑，都没讲边是给出的。

考虑还是行列式来搞，如果 (forall 1le ile k,n_1=n_i=n_k)​​ ，那么显然答案就是所有矩阵的行列式的乘积。

然后我们知道矩阵的行列式的成绩就是矩阵的乘积的行列式，然后就做完了。盲猜一波结论，搞定。

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈我TM行列式都写错了哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e2+5,K=1e2+5;
const int MOD=998244353;
int k,n[K],m[K];
int ksm(int x,int k){
	int res=1;
	for(;k;k>>=1,x=1ll*x*x%MOD)
	if(k&1) res=1ll*res*x%MOD;
	return res;
}
struct Matrix{int n,m,h[N][N];}e[K];
Matrix operator * (const Matrix a,const Matrix b){
	Matrix res;res.n=a.n,res.m=b.m;
	memset(res.h,0,sizeof(res.h));
	for(int i=1;i<=a.n;++i){
		for(int j=1;j<=a.m;++j){
			for(int k=1;k<=b.m;++k)
			(res.h[i][k]+=1ll*a.h[i][j]*b.h[j][k]%MOD)%=MOD;
		}
	}
	return res;
}
int Work(Matrix &a){
	int res=1;
	if(a.n!=a.m) return 0;
	for(int i=1;i<=a.n;++i){
		for(int j=i+1;j<=a.n;++j){
			if(a.h[i][i]>=a.h[j][i]) continue;
			swap(a.h[i],a.h[j]),res=MOD-res;
		}
		res=1ll*res*a.h[i][i]%MOD;
		if(!a.h[i][i]) break;
		for(int j=i+1;j<=a.n;++j){
			int tmp=1ll*(MOD-a.h[j][i])*ksm(a.h[i][i],MOD-2)%MOD;
			for(int k=i;k<=a.n;++k) (a.h[j][k]+=1ll*a.h[i][k]*tmp%MOD)%=MOD;
		}
	}
	return res;
}
void solve(){
	scanf("%d",&k);
	for(int i=1;i<=k;++i) scanf("%d",&n[i]);
	for(int i=1;i<k;++i) scanf("%d",&m[i]);
	for(int i=1;i<k;++i){
		e[i].n=n[i],e[i].m=n[i+1];
		memset(e[i].h,0,sizeof(e[i].h));
		for(int j=1,u,v;j<=m[i];++j){
			scanf("%d%d",&u,&v),e[i].h[u][v]++;
		}
	}
	for(int i=2;i<k;++i) e[i]=e[i-1]*e[i];
	return printf("%d
",Work(e[k-1])),void();
}
int main(){
	// freopen("xpath2.in","r",stdin);
	// freopen("xpath.out","w",stdout);
	int T;cin>>T;
	while(T--) solve();
}

celebration

图论题是根本没有想法。。。

我们考虑到缩点后是会变成一棵外向树，证明很简单，略了。

关于如何建这棵树和去掉多余边，可以用拓扑排序，最后一条删掉的入边对应顶点即为父亲节点。

这样的话我们考虑询问两点之间的可能经过的城市个数就相当于在树上搞。

如果 (k=0) 的话，相当于就是一个路径求和。

如果 (k=1) 的话，也相当于是一个类似路径求和的东西。

我们思考一下什么类型的边会对我们的答案产生影响。

如果是前向边，那么他丝毫不会影响我们可能经过的城市个数。

如果是横叉边，如果是起点位于出发点的子树内部，终点是结束点的祖先，也是可以贡献的。

如果是反祖边，只要起点位于出发点的子树内部，我们就可以通过终点来更新我们的出发点。

如果 (k=2) 的话：

如果有一条前向边，发现无论如何前向边都是没有用的，我们可以直接无视，这样就变成了一条边的情况。

如果是两条横叉边，只有在横叉边是存在一去一回的情况下才是可以做出贡献的。

如果是两条返祖边，就直接看谁返回得更高。

如果是一条横叉边，一条返祖边，就先走返祖边，再看横叉边有没有用。

好屎啊，分类讨论司马。

我们考虑有没有更加优秀的做法来搞他。

不会了，看题解。

题解好像有两种解法，一种就是大分类讨论，还有一种 ( ext{ix35}) 的做法，但是我看不懂。

好像大概意思就是你反复加边来更新我们能到达的位置。

代码

是两只 (log_2) 的，还有巨大常数，没过，也不想改了。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,M=6e5+5;
int q,k;
struct E__e{int from,to;}a[M];
struct Edge{int nxt,to;};
struct Graph{
	int n,m;
	Edge e[M];int fir[N],siz_e;
	void add(int u,int v){e[++siz_e]=(Edge){fir[u],v},fir[u]=siz_e;}
	int dfn[N],low[N],cnt_dfn;bool tag[N];stack<int> s;
	int bel[N],siz[N],cnt_bel;
	void tarjan(int u){
		dfn[u]=low[u]=++cnt_dfn,s.push(u),tag[u]=true;
		for(int i=fir[u];i;i=e[i].nxt){
			if(!dfn[e[i].to]) tarjan(e[i].to),low[u]=min(low[u],low[e[i].to]);
			else if(tag[e[i].to]) low[u]=min(low[u],dfn[e[i].to]);
		}
		if(dfn[u]==low[u]){
			++cnt_bel;
			while(s.top()!=u){
				bel[s.top()]=cnt_bel,tag[s.top()]=false;
				siz[cnt_bel]++,s.pop();
			}
			bel[s.top()]=cnt_bel,tag[s.top()]=false;
			siz[cnt_bel]++,s.pop();
		}
	}
}g;
struct Tree{
	int rt,n;
	Edge e[N];int fir[N],siz_e;
	void add(int u,int v){e[++siz_e]=(Edge){fir[u],v},fir[u]=siz_e;}
	struct Node{int fa,son,top,size,dep,L,R;}tr[N];int dfn[N],cnt_dfn;
	void dfs1(int u){
		tr[u].size=1,tr[u].top=u;
		tr[u].dep=tr[tr[u].fa].dep+1;
		for(int i=fir[u];i;i=e[i].nxt){
			tr[e[i].to].fa=u,dfs1(e[i].to),tr[u].size+=tr[e[i].to].size;
			if(tr[tr[u].son].size<tr[e[i].to].size) tr[u].son=e[i].to;
		}
	}
	void dfs2(int u){
		dfn[++cnt_dfn]=u,tr[u].L=cnt_dfn;
		if(tr[u].son) tr[tr[u].son].top=tr[u].top,dfs2(tr[u].son);
		for(int i=fir[u];i;i=e[i].nxt) if(e[i].to!=tr[u].son) dfs2(e[i].to);
		tr[u].R=cnt_dfn;
	}
}t;
struct GRAPH{
	int n;
	Edge e[M];int fir[N],deg[N],siz_e;queue<int> q;
	void add(int u,int v){e[++siz_e]=(Edge){fir[u],v},fir[u]=siz_e;}
	void top(){
		for(int i=1;i<=n;++i) if(!deg[i]) q.push(i);
		while(!q.empty()){
			int u=q.front();q.pop();
			for(int i=fir[u];i;i=e[i].nxt){
				deg[e[i].to]--;if(deg[e[i].to]) continue;
				t.add(u,e[i].to),q.push(e[i].to);
			}
		}
	}
}G;
struct Seg_Tree{
	struct Node{int len,sum,res,data[2],tag[2];}tr[N<<2];
	void up(int u){
		if(tr[u].tag[0]) tr[u].data[0]=tr[u].sum;
		else tr[u].data[0]=tr[u].len>1?tr[u<<1].data[0]+tr[u<<1|1].data[0]:0;
		if(tr[u].tag[1]) tr[u].data[1]=tr[u].sum;
		else tr[u].data[1]=tr[u].len>1?tr[u<<1].data[1]+tr[u<<1|1].data[1]:0;
		if(tr[u].tag[0]||tr[u].tag[1]) tr[u].res=min(tr[u].data[0],tr[u].data[1]);
		else tr[u].res=tr[u].len>1?tr[u<<1].res+tr[u<<1|1].res:0;
	}
	void update(int u,int z0,int z1){
		return tr[u].tag[0]+=z0,tr[u].tag[1]+=z1,up(u);
	}
	void build(int u,int l,int r){
		tr[u].len=r-l+1;if(l==r) return tr[u].sum=g.siz[t.dfn[l]],up(u);
		int mid=(l+r)>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);
		return tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum,up(u);
	}
	void modify(int u,int l,int r,int x,int y,int z0,int z1){
		if(x<=l&&r<=y) return update(u,z0,z1);
		int mid=(l+r)>>1;
		if(x<=mid) modify(u<<1,l,mid,x,y,z0,z1);
		if(y>mid) modify(u<<1|1,mid+1,r,x,y,z0,z1);
		return up(u);
	}
	int query0(int u,int l,int r,int x){
		if(l==r) return tr[u].tag[0];
		int mid=(l+r)>>1;
		if(x<=mid) return tr[u].tag[0]|query0(u<<1,l,mid,x);
		else return tr[u].tag[0]|query0(u<<1|1,mid+1,r,x);
	}
	int query1(int u,int l,int r,int x){
		if(l==r) return tr[u].tag[1];
		int mid=(l+r)>>1;
		if(x<=mid) return tr[u].tag[1]|query1(u<<1,l,mid,x);
		else return tr[u].tag[1]|query1(u<<1|1,mid+1,r,x);
	}
}T;
struct Opt{int x,y,z0,z1;};vector<Opt> bag;
void Subtree(int u){
	T.modify(1,1,t.n,t.tr[u].L,t.tr[u].R,1,0);
	bag.push_back((Opt){t.tr[u].L,t.tr[u].R,1,0});
}
void Ancestor(int u){
	while(u){
		T.modify(1,1,t.n,t.tr[t.tr[u].top].L,t.tr[u].L,0,1);
		bag.push_back((Opt){t.tr[t.tr[u].top].L,t.tr[u].L,0,1});
		u=t.tr[t.tr[u].top].fa;
	}
}
void recover(){
	for(int i=0;i<(int)bag.size();++i)
	T.modify(1,1,t.n,bag[i].x,bag[i].y,-bag[i].z0,-bag[i].z1);
	bag.clear();
}
int main(){
	// freopen("celebration5.in","r",stdin);
	// freopen("celebration.out","w",stdout);
	scanf("%d%d%d%d",&g.n,&g.m,&q,&k);
	for(int i=1;i<=g.m;++i){
		scanf("%d%d",&a[i].from,&a[i].to);
		g.add(a[i].from,a[i].to);
	}
	for(int i=1;i<=g.n;++i) if(!g.dfn[i]) g.tarjan(i);
	for(int i=1;i<=g.m;++i){
		if(g.bel[a[i].from]==g.bel[a[i].to]) continue;
		G.add(g.bel[a[i].from],g.bel[a[i].to]);
		G.deg[g.bel[a[i].to]]++;
	}
	for(int i=1;i<=g.cnt_bel;++i) if(!G.deg[i]) t.rt=i;
	G.n=t.n=g.cnt_bel,G.top();
	t.dfs1(t.rt),t.dfs2(t.rt),T.build(1,1,t.n);
	for(int i=1;i<=q;++i){
		int u[3],v[3];
		for(int j=0;j<=k;++j){
			scanf("%d%d",&u[j],&v[j]);
			u[j]=g.bel[u[j]],v[j]=g.bel[v[j]];
		}
		Subtree(u[0]),Ancestor(v[0]);
		if(k>0){
			if(T.query0(1,1,t.n,t.tr[u[1]].L)) Subtree(v[1]);
			if(T.query1(1,1,t.n,t.tr[v[1]].L)) Ancestor(u[1]);
		}
		if(k==2){
			if(T.query0(1,1,t.n,t.tr[u[2]].L)) Subtree(v[2]);
			if(T.query1(1,1,t.n,t.tr[v[2]].L)) Ancestor(u[2]);
			if(T.query0(1,1,t.n,t.tr[u[1]].L)) Subtree(v[1]);
			if(T.query1(1,1,t.n,t.tr[v[1]].L)) Ancestor(u[1]);
		}
		printf("%d
",T.tr[1].res),recover();
	}
}

Day2

qi

有理由怀疑这题是清华出的。

首先我们考虑最多是有 (15)​ 个位置改变了，如果我们将原本 (256) 位的 (01) 串拆分成 (16) 位一组。

这样的话至少有一组是完全一样的，我们考虑枚举这个一样的组是哪一个。

由于字典是随机生成的，所以我们的复杂度是可以保证的。

首先对于在同一组内的个数期望应该是 (frac{n}{2^{16}})​​​​​​​ ，然后对于每一个，我们的查询时间应该是 (256)​​​​​​​ ，所以我们的总复杂度应该是 (mcdot 16cdot frac{n}{2^{16}}cdot 16=frac{nm}{256})​​​​​​​​ 。

代码

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=400001;
int n,m;ull a1,a2;
int cnt[1<<16];
int s[N][16],lstans=0;
ull myRand(ull &k1, ull &k2) {
	ull k3=k1,k4=k2;
	k1=k4,k3^=(k3<<23),k2=k3^k4^(k3>>17)^(k4>>26);
	return k2+k4;
}
void gen(int n, ull a1, ull a2) {
	for(int i=1;i<=n;++i)
		for(int j=0;j<16;++j)
			for(int k=0;k<16;++k)
				s[i][j]=(s[i][j]<<1)+((myRand(a1,a2)&(1ull<<32))?1:0);
}
int read(){
	int x=0;
	for(int i=0;i<4;++i){
		char c=getchar();
		while((c<'0'||'9'<c)&&(c<'A'||'F'<c)) c=getchar();
		x=(x<<4)+(('0'<=c&&c<='9')?(c-'0'):(c-'A'+10));
	}
	return x;
}
vector<int> bag[16][1<<16];
int main(){
	// freopen("qi1.in","r",stdin);
	// freopen("qi.out","w",stdout);
	for(int i=0;i<(1<<16);++i)
		cnt[i]=cnt[i>>1]+(i&1);
	cin>>n>>m>>a1>>a2,gen(n,a1,a2);
	for(int i=1;i<=n;++i){
		for(int j=0;j<16;++j)
		bag[j][s[i][j]].push_back(i);
	}
	for(int i=1;i<=m;++i){
		int t[16],lim;
		for(int j=0;j<16;++j) t[j]=read();
		if(lstans){
			for(int j=0;j<16;++j)
				t[j]=(((1<<16)-1)^t[j]);
		}
		lstans=0,scanf("%d",&lim);
		for(int j=0;j<16;++j){
			for(int k=0;k<(int)bag[j][t[j]].size();++k){
				int sum=0;
				for(int c=0;c<16;++c)
					sum+=cnt[s[bag[j][t[j]][k]][c]^t[c]];
				if(sum<=lim) lstans=1;
				if(lstans) break;
			}
			if(lstans) break;
		}
		printf("%d
",lstans);
	}
	return 0;
}

code

感觉只有这个 (T2) 有点感觉，先看一看。

我们发现对于同一对末尾数的操作一定是这样的 (EE…EWW…WE) ，因为只要先出现了一个 (W) ，之后只要出现了 (E) 就行进行下一步操作。

我们考虑可以将整个操作序列分成 (EE…EWW…W)​ ，这种的若干个子串，每一个字串的 (E) 的个数记为 (cnt_e) ， (W) 的个数记为 (cnt_w) 。

易发现，第 (i) 个串的 (a_{2i-2},a_{2i-1}) 为：

[a_{2i-2}=cnt_e\
a_{2i-1}=cnt_w
]

但是最后一个串的 (cnt_w) 需加一，这个特判一下即可。

我们把 (E) 操作看作 (0) ，(W) 操作看作 (1) ，我们可以将题意直接转换。

给你一个 (01) 串，需要区间反转，区间翻转，末尾加一个数，问你他的权值是多少。

权值的定义为现在序列末尾加一个 (1)​ ，然后问你有多少种选择 (0101…01)​ 序列的方案和多少种选择 (1010…101)​ 的方案，其中第一个答案在输出时还需要 (+1) 。

我们考虑 (Splay) 可不可以干这个。

发现是可以的。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
const int MOD=998244353;
int n,q;
struct splay{
	int rt;
	struct Node{
		int fa,son[2];
		int size,data,f[2][2];
		bool tag_F,tag_R;
	}tr[N];
	void up(int u){
		if(!u) return ;
		memset(tr[u].f,0,sizeof(tr[u].f));
		if(tr[u].data>=0){
			tr[u].f[tr[u].data][tr[u].data]=1;
			for(int c=0;c<2;++c){
				tr[u].f[c][tr[u].data]+=tr[tr[u].son[0]].f[c][tr[u].data^1];
				tr[u].f[c][tr[u].data]%=MOD;
			}
			for(int c=0;c<2;++c){
				tr[u].f[tr[u].data][c]+=tr[tr[u].son[1]].f[tr[u].data^1][c];
				tr[u].f[tr[u].data][c]%=MOD;
			}
			for(int c=0;c<2;++c){
				for(int d=0;d<2;++d){
					tr[u].f[c][d]+=1ll*tr[tr[u].son[0]].f[c][tr[u].data^1]*tr[tr[u].son[1]].f[tr[u].data^1][d]%MOD;
					tr[u].f[c][d]%=MOD;
				}
			}
		}
		for(int c=0;c<2;++c){
			for(int d=0;d<2;++d){
				tr[u].f[c][d]+=tr[tr[u].son[0]].f[c][d];
				tr[u].f[c][d]%=MOD;
			}
		}
		for(int c=0;c<2;++c){
			for(int d=0;d<2;++d){
				tr[u].f[c][d]+=tr[tr[u].son[1]].f[c][d];
				tr[u].f[c][d]%=MOD;
			}
		}
		for(int c=0;c<2;++c){
			for(int d=0;d<2;++d){
				tr[u].f[c][d]+=1ll*tr[tr[u].son[0]].f[c][0]*tr[tr[u].son[1]].f[1][d]%MOD;
				tr[u].f[c][d]%=MOD;
				tr[u].f[c][d]+=1ll*tr[tr[u].son[0]].f[c][1]*tr[tr[u].son[1]].f[0][d]%MOD;
				tr[u].f[c][d]%=MOD;
			}
		}
		tr[u].size=tr[tr[u].son[0]].size+tr[tr[u].son[1]].size+1;
	}
	void update(int u,bool tag_F,bool tag_R){
		if(!u) return ;
		if(tag_F){
			swap(tr[u].f[0][0],tr[u].f[1][1]);
			swap(tr[u].f[0][1],tr[u].f[1][0]);
			tr[u].data^=1,tr[u].tag_F^=1;
		}
		if(tag_R){
			swap(tr[u].f[0][1],tr[u].f[1][0]);
			swap(tr[u].son[0],tr[u].son[1]);
			tr[u].tag_R^=1;
		}
	}
	void down(int u){
		update(tr[u].son[0],tr[u].tag_F,tr[u].tag_R);
		update(tr[u].son[1],tr[u].tag_F,tr[u].tag_R);
		tr[u].tag_F=0,tr[u].tag_R=0;
	}
	int get_son(int u){return tr[tr[u].fa].son[1]==u;}
	void Rotate(int u){
		int fa=tr[u].fa,gfa=tr[fa].fa,k=get_son(u);
		down(u),down(fa);if(gfa) tr[gfa].son[get_son(fa)]=u;
		tr[fa].son[k]=tr[u].son[!k],tr[tr[u].son[!k]].fa=fa;
		tr[u].son[!k]=fa,tr[fa].fa=u,tr[u].fa=gfa;
		return up(fa),up(u);
	}
	void Splay(int u,int go){
		for(int fa=tr[u].fa;fa!=go;Rotate(u),fa=tr[u].fa)
		if(tr[fa].fa!=go) Rotate(get_son(u)==get_son(fa)?fa:u);
		if(!go) rt=u;
	}
	int find(int u,int rk){
		down(u);
		if(tr[tr[u].son[0]].size+1==rk) return Splay(u,0),u;
		if(tr[tr[u].son[0]].size>=rk) return find(tr[u].son[0],rk);
		else return find(tr[u].son[1],rk-tr[tr[u].son[0]].size-1);
	}
	void Split(int u,int v,bool tag_F,bool tag_R){
		int U=find(rt,u),V=find(rt,v);
		Splay(U,0),Splay(V,U),update(tr[V].son[0],tag_F,tag_R);
	}
}t;
int main(){
	// freopen("code1.in","r",stdin);
	// freopen("code.out","w",stdout);
	cin>>n>>q,++n;
	t.rt=1;
	for(int i=1;i<=n+q+5;++i){
		t.tr[i].fa=i-1,t.tr[i-1].son[1]=(i!=1)?i:0;
		t.tr[i].data=-1;
	}
	for(int i=n+q+5;i>=1;--i) t.up(i);
	for(int i=2;i<=n;++i){
		char c=getchar();
		while(c!='W'&&c!='E') c=getchar();
		t.Splay(i,0),t.tr[i].data=(c=='W'),t.up(i);
	}
	t.Splay(n+1,0),t.tr[n+1].data=1,t.up(n+1);
	printf("%d %d
",(t.tr[n+1].f[0][1]+1)%MOD,t.tr[n+1].f[1][1]);
	for(int i=1;i<=q;++i){
		char opt[10];int u,v;char c;
		scanf("%s",opt);
		if(opt[0]=='A'){
			c=getchar();
			while(c!='W'&&c!='E') c=getchar();
			t.Splay(++n,0),t.tr[n].data=(c=='W'),t.up(n);
		}
		if(opt[0]=='F'){
			scanf("%d%d",&u,&v),u++,v++;
			t.Split(u-1,v+1,true,false);
		}
		if(opt[0]=='R'){
			scanf("%d%d",&u,&v),u++,v++;
			t.Split(u-1,v+1,false,true);
		}
		t.Splay(n+1,0),t.tr[n+1].data=1,t.up(n+1);
		printf("%d %d
",(t.tr[n+1].f[0][1]+1)%MOD,t.tr[n+1].f[1][1]);
		// for(int k=2,j;k<=n+1;++k){
		// 	j=t.find(t.rt,k),t.Splay(j,0);
		// 	printf("%d %d %d %d %d %d
",j,t.tr[j].data,t.tr[j].f[0][0],t.tr[j].f[0][1],t.tr[j].f[1][0],t.tr[j].f[1][1]);
		// }
	}
	return 0;
}

admin

相关文章

python
对嵌入字符串中的数字进行排序
3月 7, 2023 [db:作者]
python
如何使用Pandas对excel文件中的数据进行排序。并对副本进行排序
3月 7, 2023 [db:作者]
python
在pygtk Treevi中添加新行
3月 7, 2023 [db:作者]

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

You missed

python
python
python
python