Logo __vector__ 的博客

博客

How to AK ABC265

...
__vector__
2025-12-01 12:55:48

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-08-21 22:01:09

题外话

第一次打出 $1200$ 以上的表现分，上绿了。

A&B&C

略过

D

枚举每一个位置作为 $x$，然后利用前缀和二分得出 $y,z,w$。

E

设状态 $dp_{i,j,k}$ 表示第一种组合使用数量为 $i$，第二种组合使用数量为 $j$，第三种组合数量为 $k$ 的方案数。

#include <bits\/stdc++.h>
using namespace std;
namespace Main {
	typedef long long ll;
	const ll mod=998244353;
	const int maxn=305;
	map<pair<ll,ll>,bool> mp;
	ll f[maxn][maxn][maxn];
	int n,m;
	ll A,B,C,D,E,F;
	void main() {
		scanf("%d%d",&n,&m);
		scanf("%lld%lld%lld%lld%lld%lld",&A,&B,&C,&D,&E,&F);
		ll x,y;
		for(int i=1; i<=m; i++) {
			scanf("%lld%lld",&x,&y);
			mp[make_pair(x,y)]=1;
		}
		f[0][0][0]=1;
		for(ll i=0; i<=n; i++) {
			for(ll j=0; j<=n-i; j++) {
				for(ll k=0; k<=n-i-j; k++) {
					if(mp[make_pair(i*A+j*C+k*E,i*B+j*D+k*F)]) {
						continue;
					}
					if(i) {
						f[i][j][k]+=f[i-1][j][k];
					}
					if(j) {
						f[i][j][k]+=f[i][j-1][k];
					}
					if(k) {
						f[i][j][k]+=f[i][j][k-1];
					}
					f[i][j][k]%=mod;
				}
			}
		}
		ll ans=0;
		for(ll i=0; i<=n; i++) {
			for(ll j=0; j<=n-i; j++) {
				ll k=n-i-j;
				ans+=f[i][j][k];
				ans%=mod;
			}
		}
		printf("%lld",ans);
	}
}
int main() {
	Main::main();
	return 0;
}

F

在想

G

这道题由于我之前维护 $6$ 个 tag 的做法假了，所以我只会邹神的做法。 我搞的分块做法 AC了。
感觉 $6$ 个 tag 的做法应该还是能做的，但是修改很麻烦，我一个 pushdown 能写几十行。

区间逆序对的数量由 $(1,0),(2,0),(2,1)$ 这样数对的数量决定。

维护序列，那就用线段树。

想一下如何合并左右子树信息（就是怎么让左右子树信息可以相加得到当前信息）。

显然是左右子树区间各自的逆序对数，以及左右子树区间之间形成的逆序对数相加。（也就说明了和左右子树区间原本的答案，以及左右区间各自的每个数出现的次数有关）

所以：

对于每一个节点，用 $g_{i,j}$ 维护它对应的区间的逆序对数（相当于记录自己原本的答案，合并到父节点时要用到），具体是：有多少个数值 $i$ 在数值 $j$ 前面。

同时每个节点都还要维护一个 $cnt$ 数组，代表它对应的区间每个值出现次数，方便合并信息。

左右子树合并信息时，用各自的 $g$ 数组和 $cnt$ 数组就能快速（常数时间）得到结果了。现在

那修改操作怎么办？

每个节点维护一个数组 $turn$ 代表这个节点对应的区间每个数应该以什么形式转换。（相当于对于子树的 lazy_tag）

进行修改时，就在标记下方的时候，按照常规操作，把子树的 lazy_tag 加上当前的 lazy_tag，并将子树的信息按照本节点的 lazy_tag 进行转换。

查询的时候，就将查找区间内找到的几个节点记录下来，直接把对应区间记录的信息扒下来就行了，注意一个区间可以由好几个节点组成，要将这几个节点按照左右顺序合并再输出答案（合并方式就是之前所说的合并左右子树的方式，直接相加信息）
$O(n + q\log n)$

#include <bits\/stdc++.h>
using namespace std;
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
namespace Main {
	typedef long long ll;
	const int maxn=1e5+5;
	int n;
	int a[maxn];
	int q;
	struct Replace {
		int turn[3];
		void init() {
			turn[0]=0;
			turn[1]=1;
			turn[2]=2;
		}
		Replace operator +(const Replace& b) {
			Replace res;
			for(int i=0; i<3; i++) {
				res.turn[i]=b.turn[turn[i]];
			}
			return res;
		}
	};
	struct Information {
		ll g[3][3];
		ll cnt[3];
		Information() {
			memset(g,0,sizeof g);
			memset(cnt,0,sizeof cnt);
		}
		Information operator +(const Information& b) {
			Information res;
			for(int i=0; i<3; i++)res.cnt[i]=cnt[i]+b.cnt[i];
			for(int i=0; i<3; i++) {
				for(int j=0; j<3; j++) {
					res.g[i][j]=g[i][j]+b.g[i][j];
					res.g[i][j]+=cnt[i]*b.cnt[j];
				}
			}
			return res;
		}
		ll sum()
		{
			ll res=0;
			for(int i=0;i<3;i++)
			{
				for(int j=0;j<i;j++)
				{
					res+=g[i][j];
				}
			}
			return res;
		}
	};
	Information Modify(Information information,Replace replace) {
		Information res;
		for(int i=0; i<3; i++) {
			res.cnt[replace.turn[i]]+=information.cnt[i];
		}
		for(int i=0; i<3; i++) {
			for(int j=0; j<3; j++) {
				res.g[replace.turn[i]][replace.turn[j]]+=information.g[i][j];
			}
		}
		return res;
	}
	struct Tree {
		Information information;
		Replace replace_tag;
		int l,r;
	} tree[maxn<<2];
	void pushup(int i)
	{
		tree[i].information=tree[ls(i)].information+tree[rs(i)].information;
	}
	void pushdown(int i)
	{
		tree[ls(i)].replace_tag=tree[ls(i)].replace_tag+tree[i].replace_tag;
		tree[ls(i)].information=Modify(tree[ls(i)].information,tree[i].replace_tag);
		tree[rs(i)].replace_tag=tree[rs(i)].replace_tag+tree[i].replace_tag;
		tree[rs(i)].information=Modify(tree[rs(i)].information,tree[i].replace_tag);
		tree[i].replace_tag.init();
	}
	void build(int i,int l,int r)
	{
		tree[i].l=l;
		tree[i].r=r;
		tree[i].replace_tag.init();
		if(l==r)
		{
			tree[i].information.cnt[a[l]]=1;
			return;
		}
		int mid=l+r>>1;
		build(ls(i),l,mid);
		build(rs(i),mid+1,r);
		pushup(i);
	}
	
	void change(int i,int l,int r,Replace replace)
	{
		if(tree[i].l>=l&&tree[i].r<=r)
		{
			tree[i].replace_tag=tree[i].replace_tag+replace;
			tree[i].information=Modify(tree[i].information,replace);
			return;
		}
		if(tree[i].r<l||tree[i].l>r)return;
		pushdown(i);
		int mid=tree[i].l+tree[i].r>>1;
		if(mid>=l)change(ls(i),l,r,replace);
		if(mid<r)change(rs(i),l,r,replace);
		pushup(i);
	}
	Information query(int i,int l,int r)
	{
		if(tree[i].l>=l&&tree[i].r<=r)
		{
			return tree[i].information;
		}
		pushdown(i);
		int mid=tree[i].l+tree[i].r>>1;
		Information ans;
		if(mid>=l)ans=ans+query(ls(i),l,r);
		if(mid<r)ans=ans+query(rs(i),l,r);
		return ans;
	}
	void main() {
		scanf("%d%d",&n,&q);
		for(int i=1; i<=n; i++) {
			scanf("%d",&a[i]);
		}
		build(1,1,n);
		int op,l,r,s,t,u;
		while(q--) {
			scanf("%d",&op);
			if(op==1)
			{
				scanf("%d%d",&l,&r);
				printf("%lld\n",query(1,l,r).sum());
			}
			if(op==2)
			{
				scanf("%d%d%d%d%d",&l,&r,&s,&t,&u);
				Replace rep;
				rep.turn[0]=s;
				rep.turn[1]=t;
				rep.turn[2]=u;
				change(1,l,r,rep);
			}
		}
	}
}
int main() {
	Main::main();
	return 0;
}

我再说一下这道题的分块做法。

我的做法是，整块打 lazytag 进行修改，散块暴力修改，同时维护区间答案。

查询时整块直接查询区间答案加上lazytag，散块暴力（也要加上所在块的 lazytag），同时将查询到的信息合并。

来说一下细节：

  1. 对整块修改时，将区间的 lazytag 根据 $S,T,U$ 进行转换。
  2. 对散块修改时，暴力修改元素的时候，不仅还要算上本次修改的，还要算上本区间之前的 lazytag（如果这个区间还有 tag，那说明之前没修改完）。另外由于本次修改时已经算上了之前的 lazytag，还要将对应区间的 lazytag 去掉，防止当前修改的这些元素被重复修改。但是这个区间有的元素之前被打了修改标记，但是当前并没有完成修改，直接去掉区间 lazytag 会导致漏修改这些元素，所以还要把那些 lazytag 被去掉但是之前的修改没有被应用的元素，在 lazytag 去掉之前完成修改（显然这个修改就要根据本区间原来已有的tag，而不包括本次修改加上的 tag了）。

总结一句话，细节超多。
$O(n+q \sqrt n)$

#include <bits\/stdc++.h>
using namespace std;
namespace Main {
	typedef long long ll;
	const int maxn=1e5+5;
	int n;
	int a[maxn];
	int q;
	struct Replace {
		int turn[3];
		void init() {
			turn[0]=0;
			turn[1]=1;
			turn[2]=2;
		}
		Replace operator +(const Replace& b) {
			Replace res;
			for(int i=0; i<3; i++) {
				res.turn[i]=b.turn[turn[i]];
			}
			return res;
		}
	};
	struct Information {
		ll g[3][3];
		ll cnt[3];
		Information() {
			memset(g,0,sizeof g);
			memset(cnt,0,sizeof cnt);
		}
		Information operator +(const Information& b) {
			Information res;
			for(int i=0; i<3; i++)res.cnt[i]=cnt[i]+b.cnt[i];
			for(int i=0; i<3; i++) {
				for(int j=0; j<3; j++) {
					res.g[i][j]=g[i][j]+b.g[i][j];
					res.g[i][j]+=cnt[i]*b.cnt[j];
				}
			}
			return res;
		}
		ll sum()
		{
			ll res=0;
			for(int i=0;i<3;i++)
			{
				for(int j=0;j<i;j++)
				{
					res+=g[i][j];
				}
			}
			return res;
		}
	};
	Information Modify(Information information,Replace replace) {
		Information res;
		for(int i=0; i<3; i++) {
			res.cnt[replace.turn[i]]+=information.cnt[i];
		}
		for(int i=0; i<3; i++) {
			for(int j=0; j<3; j++) {
				res.g[replace.turn[i]][replace.turn[j]]+=information.g[i][j];
			}
		}
		return res;
	}
	int blocks,len;
	int id[maxn];
	Information lazy[maxn];\/\/记录块整体信息 
	Replace lazyrep[maxn];
	Information val[maxn];\/\/单个元素信息 
	int L[maxn],R[maxn];\/\/每个块的左右端点 
	ll query(int l,int r)
	{
		Information res;
		if(id[l]==id[r])
		{
			for(int i=l;i<=r;i++)
			{
				res=res+Modify(val[i],lazyrep[id[l]]);
			}
			return res.sum();
		}
		if(id[l]!=id[r])
		{
			for(int i=l;i<=R[id[l]];i++)
			{
				res=res+Modify(val[i],lazyrep[id[l]]);
			}
			for(int i=id[l]+1;i!=id[r];i++)
			{
				res=res+Modify(lazy[i],lazyrep[i]);
			}
			for(int i=L[id[r]];i<=r;i++)
			{
				res=res+Modify(val[i],lazyrep[id[r]]);
			}
			return res.sum();
		}
	}
	void change(int l,int r,Replace replace)
	{
		if(id[l]==id[r])
		{
			for(int i=l;i<=r;i++)
			{
				val[i]=Modify(val[i],lazyrep[id[l]]+replace);
			}
			Information tmp;
			for(int i=L[id[l]];i<=R[id[l]];i++)
			{
				if(i<l||i>r)
				    val[i]=Modify(val[i],lazyrep[id[l]]);
				tmp=tmp+val[i];
			}
			lazy[id[l]]=tmp;
			lazyrep[id[l]].init();
		}
		if(id[l]!=id[r])
		{
			for(int i=l;i<=R[id[l]];i++)
			{
				val[i]=Modify(val[i],lazyrep[id[l]]+replace);
			}
			Information tmp;
			for(int i=L[id[l]];i<=R[id[l]];i++)
			{
				if(i<l)
				    val[i]=Modify(val[i],lazyrep[id[l]]);
				tmp=tmp+val[i];
			}
			lazy[id[l]]=tmp;
			lazyrep[id[l]].init();
			for(int i=id[l]+1;i!=id[r];i++)
			{
				lazyrep[i]=lazyrep[i]+replace;
			}
			for(int i=L[id[r]];i<=r;i++)
			{
				val[i]=Modify(val[i],lazyrep[id[r]]+replace);
			}
			Information tmp2;
			for(int i=L[id[r]];i<=R[id[r]];i++)
			{
				if(i>r)
				    val[i]=Modify(val[i],lazyrep[id[r]]);
				tmp2=tmp2+val[i];
			}
			lazy[id[r]]=tmp2;
			lazyrep[id[r]].init();
		}
	}
	void main() {
		scanf("%d%d",&n,&q);
		len=sqrt(n);
		for(int i=1; i<=n; i++) {
			scanf("%d",&a[i]);
			val[i].cnt[a[i]]++;
			id[i]=(i-1)\/len+1;
			lazy[id[i]]=lazy[id[i]]+val[i];
		}
\/\/		printf("sum: %lld\n",lazy[1].sum());
		for(int i=1;i<=n;i++)
		{
			if(id[i]!=id[i-1])
			{
				L[id[i]]=i;
			}
			if(id[i]!=id[i+1])
			{
				R[id[i]]=i;
			}
			lazyrep[id[i]].init();
		}
		int op,l,r,s,t,u;
		while(q--) {
			scanf("%d",&op);
			if(op==1)
			{
				scanf("%d%d",&l,&r);
				printf("%lld\n",query(l,r));
			}
			if(op==2)
			{
				scanf("%d%d%d%d%d",&l,&r,&s,&t,&u);
				Replace rep;
				rep.turn[0]=s;
				rep.turn[1]=t;
				rep.turn[2]=u;
				change(l,r,rep);
			}
		}
	}
}
int main() {
	Main::main();
	return 0;
}

Ex

在想

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

中文 English

鲁ICP备2025150228号

服务器时间: 2025-12-19 16:11:40 | 开源项目