2023.1.28~2023.1.30 日寄

标签：ch int ll 30 28 while dep 2023.1 getchar

2023.1.28~2023.1.30

猜猜看为什么会积压三天？看看前两天在干什么吧。

一言(1.28)

我会被音乐打动、被诗歌打动，如果有一天我不再被打动了，我就会死。你知道我的意思吗？被打动实在太重要了。
\(~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\) ————安塞姆·弗基

2023.1.28:分块

「Ynoi Easy Round 2020」TEST_100

题解

\(~~~~\) 根据复习内容可知使用序列分块，那我们为了快速过整块就需要处理每个数过一个整块过后变成什么数。这大约需要在 \(\mathcal{O(n)\sim \mathcal{O(n\log n)}}\) 完成一个块内的处理。

\(~~~~\) 注意到一个类似于维护分段函数的方法，下移过后绝对值函数会进行翻折，那我们每次都对较短的一段把它的值直接用对应的值去代替，每个数只会去合并其他的一次，那用并查集就可以 \(\mathcal{O(w)}\) 处理每个块了。

代码

查看代码

#include <bits/stdc++.h>
using namespace std;
template<typename T>void read(T &x)
{
    T f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
int Val[100005];
int belong[100005],L[100005],R[100005];

int fa[100005];
void makeSet(int N){for(int i=0;i<=N;i++) fa[i]=i;}
int findSet(int x){return fa[x]==x?x:fa[x]=findSet(fa[x]);}

inline int Abs(int x){return x>=0?x:-x;}
int res[200][100005];
int main() {
	int n,m;read(n);read(m);
	for(int i=1;i<=n;i++) read(Val[i]);
	int Siz=666,Num=0;
	//记得改这里的块长 
	for(int i=1;i<=n;i++)
	{
		belong[i]=(i-1)/Siz;
		if(!L[belong[i]]) L[belong[i]]=i;
		R[belong[i]]=i; Num=belong[i];
	}
	for(int i=1;i<=Num;i++)
	{
		makeSet(100000);
		int tot=0,l=0,r=100000;bool flag=0;
		//flag为0:当前是原数-tot 为1:当前是tot-原数
		for(int j=L[i];j<=R[i];j++)
		{
			if(!flag)
			{
				int P=tot+Val[j];//翻折的对称点
				if(P<=((l+r)>>1))
				{
					for(int k=l;k<P;k++)
					{
						int x=findSet(k),y=findSet(2*P-k);
						if(x!=y) fa[x]=y;
					}
					l=max(P,l); tot+=Val[j];
				}
				else
				{
					for(int k=P+1;k<=r;k++)
					{
						int x=findSet(k),y=findSet(2*P-k);
						if(x!=y) fa[x]=y;	
					}
					r=min(P,r); tot+=Val[j]; flag=true;
				}
			}
			else
			{
				int P=tot-Val[j];//对称点
				if(P<=((l+r)>>1))
				{
					for(int k=l;k<P;k++)
					{
						int x=findSet(k),y=findSet(2*P-k);
						if(x!=y) fa[x]=y; 
					}
					l=max(P,l); tot-=Val[j]; flag=false;
				}
				else
				{
					for(int k=P+1;k<=r;k++)
					{
						int x=findSet(k),y=findSet(2*P-k);
						if(x!=y) fa[x]=y;
					}
					r=min(P,r); tot-=Val[j]; 
				}
			}
		}
		for(int j=0;j<=100000;j++)
		{
			int rt=findSet(j);
			if(!flag) res[i][j]=rt-tot;
			else res[i][j]=tot-rt;
		}
	}
	int lst=0,l,r,v;
	while(m--)
	{
		read(l);read(r);read(v);
		l^=lst; r^=lst; v^=lst;
		if(belong[l]==belong[r]) for(int i=l;i<=r;i++) v=Abs(v-Val[i]);
		else
		{
			for(int i=l;i<=R[belong[l]];i++) v=Abs(v-Val[i]);
			for(int i=belong[l]+1;i<belong[r];i++) v=res[i][v];
			for(int i=L[belong[r]];i<=r;i++) v=Abs(v-Val[i]);
		}
		printf("%d\n",lst=v);
	}
	return 0;
}
/*
西风吹老洞庭波，一夜湘君白发多。
醉后不知天在水，满船清梦压星河。
*/

「POI2015」Odwiedziny

题解

\(~~~~\) 虽然放在分块里面但其实是根号分治。

\(~~~~\) 对于每个询问，若步长 \(> \sqrt{n}\)，那每次都暴力跳跳到高于LCA处停止，显然这样最多跳 \(\sqrt{n}\) 次。

\(~~~~\) 若步长 \(\leq \sqrt{n}\)，那预处理出每次跳 \(step\in[1,\sqrt{n}]\) 步时候到这个点的前缀和，直接计算出每个点最后跳到的终点前缀和做了就好了。

\(~~~~\) 时间复杂度 \(\mathcal{O(m\sqrt{n}\log n)}\)，\(\log\) 是跳 \(k\) 级祖先来的。

代码

查看代码

#include <bits/stdc++.h>
using namespace std;
template<typename T>void read(T &x)
{
    T sig=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')sig=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    x*=sig;
}
vector <int> G[50005];
int Pre[50005][225],B;
int val[50005],a[50005],f[50005][21],dep[50005],lg[50005];
int kfa(int u,int k)
{
	if(dep[u]<k) return 0;
	for(int i=lg[dep[u]];~i;i--) 
		if((k>>i)&1) u=f[u][i];
	return u;
}
int LCA(int u,int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=lg[dep[u]];~i;i--) if(dep[f[u][i]]>=dep[v]) u=f[u][i];
	if(u==v) return u;
	for(int i=lg[dep[u]];~i;i--) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
	return f[u][0];
}
void dfs(int u,int fa)
{
	dep[u]=dep[fa]+1; f[u][0]=fa;
	for(int i=1;i<=lg[dep[u]];i++) f[u][i]=f[f[u][i-1]][i-1];
	for(int i=0;i<(int)G[u].size();i++) if(G[u][i]!=fa) dfs(G[u][i],u);
}
void dfs2(int u,int fa)
{
	for(int i=1;i<=B;i++) Pre[u][i]=Pre[kfa(u,i)][i]+val[u];
	for(int i=0;i<(int)G[u].size();i++) if(G[u][i]!=fa) dfs2(G[u][i],u);
}
int main() {
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	int n;read(n); B=sqrt(n);
	for(int i=1;i<=n;i++) read(val[i]),lg[i]=lg[i>>1]+1;
	for(int i=1,u,v;i<n;i++)
	{
		read(u);read(v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,0); 
	dfs2(1,0); 
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1,c;i<n;i++)
	{
		int x=a[i],y=a[i+1];
		read(c);
		if(c>=B)
		{
			int Ans=0,A=LCA(x,y);
			while(dep[x]>dep[A]) Ans+=val[x],x=kfa(x,c);
			while(dep[y]>dep[A]) Ans+=val[y],y=kfa(y,c);
			if(dep[x]%c==dep[y]%c&&dep[x]>0) Ans+=val[A];
			printf("%d\n",Ans);
		}
		else
		{
			int A=LCA(x,y);
			int StepA=dep[A]-(dep[A]%c+c-dep[x]%c)%c;
			int StepB=dep[A]-(dep[A]%c+c-dep[y]%c)%c;
			int ToA=kfa(x,dep[x]-StepA),ToB=kfa(y,dep[y]-StepB);
			printf("%d\n",Pre[x][c]+Pre[y][c]-Pre[ToA][c]-Pre[ToB][c]+((StepA==dep[A])?val[A]:0));
		}
	}
	return 0;
}
/*
西风吹老洞庭波，一夜湘君白发多。
醉后不知天在水，满船清梦压星河。
*/

「Ynoi2014」置身天上之森

题解

\(~~~~\) 做这道题的时候被剧透地彻彻底底。

\(~~~~\) 如果我们先考虑只在线段树的叶子结点或者说就是在一个序列上做这个问题（区间加，询问区间 \(\leq a\) 的数字个数），那我们可以序列分块完成：维护每个块的有序序列。加法时零散块暴力加+暴力重构，否则打标记。查询时零散块暴力数，否则二分找到答案。显然这是 \(\mathcal{O(m\log \sqrt{n \log n})}\)

\(~~~~\) 注意到线段树上的结点的长度总共是 \(\mathcal{O(\log n)}\) 种，所以为什么不把每个长度的区间都拉下来过一遍上面的操作呢。看起来这个做法很垃圾是 \(\mathcal{O(m\log n\sqrt{n \log n})}\)，不过你发现因为区间不一定都有 \(n\) 个，拿等比数列求一下应该还是挺优秀的。

\(~~~~\) 然后就是一大堆细节。

代码

查看代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T>void read(T &x)
{
    T f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
struct node{
	ll l,r;
	node(){}
	node(ll L,ll R){l=L,r=R;}
};
bool operator <(const node a,const node b){return a.l<b.l;}
struct Ask{
	ll op,l,r,a;
	Ask(){}
	Ask(ll Op,ll L,ll R,ll A){op=Op,l=L,r=R,a=A;}
}A[100005];
ll cnt=0,LenToId[100005],IdToLen[55];
vector <node> V[55];
ll Ans[100005];
void Build(ll l,ll r)
{
	if(!LenToId[r-l+1]) LenToId[r-l+1]=++cnt,IdToLen[cnt]=r-l+1,V[cnt].push_back(node(-1e9,-1e9));
	V[LenToId[r-l+1]].push_back(node(l,r));
	if(l==r) return;
	ll mid=(l+r)>>1;
	Build(l,mid); Build(mid+1,r);
}
struct Block{
	ll N,Siz,L[505],R[505],Tag[505],belong[100005];
	ll arr[100005],F[100005];
	void Init(ll n)
	{
		N=n; Siz=sqrt(n);
		for(ll i=1;i<=100000;i++) belong[i]=arr[i]=F[i]=0;
		for(ll i=1;i<=500;i++) L[i]=R[i]=Tag[i]=0;
		for(ll i=1;i<=n;i++)
		{
			belong[i]=(i-1)/Siz+1;	
			if(!L[belong[i]]) L[belong[i]]=i;
			R[belong[i]]=i;
		}
	}
	void Add(ll Type,ll l,ll r,ll lx,ll rx,ll Val)
	{
		if(l>r) return;
		#define Len (min(rx,V[Type][i].r)-max(lx,V[Type][i].l)+1)
		if(belong[l]==belong[r])
		{
			for(ll i=l;i<=r;i++) arr[i]+=Len*Val;
			for(ll i=L[belong[l]];i<=R[belong[l]];i++) F[i]=arr[i];
			sort(F+L[belong[l]],F+R[belong[l]]+1);
		}
		else
		{
			for(ll i=l;i<=R[belong[l]];i++) arr[i]+=Len*Val;
			for(ll i=L[belong[l]];i<=R[belong[l]];i++) F[i]=arr[i];
			sort(F+L[belong[l]],F+R[belong[l]]+1);
			
			for(ll i=belong[l]+1;i<=belong[r]-1;i++) Tag[i]+=IdToLen[Type]*Val;
			
			for(ll i=L[belong[r]];i<=r;i++) arr[i]+=Len*Val;
			for(ll i=L[belong[r]];i<=R[belong[r]];i++) F[i]=arr[i];
			sort(F+L[belong[r]],F+R[belong[r]]+1);
		}
		#undef Len 
	}
	ll Query(ll l,ll r,ll x)
	{
		if(l>r) return 0; ll res=0;
		if(belong[l]==belong[r]){for(ll i=l;i<=r;i++) res+=(arr[i]+Tag[belong[l]]<=x);return res;}
		for(ll i=l;i<=R[belong[l]];i++) res+=(arr[i]+Tag[belong[l]]<=x);
		for(ll i=belong[l]+1;i<=belong[r]-1;i++) res+=upper_bound(F+L[i],F+R[i]+1,x-Tag[i])-F-L[i];
		for(ll i=L[belong[r]];i<=r;i++) res+=(arr[i]+Tag[belong[r]]<=x);
		return res;
	}
	void DEBUG(ll Type)
	{
		for(ll i=1;i<V[Type].size();i++) printf("%lld %lld:%lld",V[Type][i].l,V[Type][i].r,arr[i]+Tag[belong[i]]),puts("");
	}
}Blo;
int main() {
	ll n,m;read(n);read(m);
	Build(1,n);
	for(ll i=1;i<=m;i++) read(A[i].op),read(A[i].l),read(A[i].r),read(A[i].a);
	for(ll Type=1;Type<=cnt;Type++)
	{
		Blo.Init(V[Type].size()-1);
		for(ll i=1;i<=m;i++)
		{
			ll L=lower_bound(V[Type].begin(),V[Type].end(),node(A[i].l,0))-V[Type].begin();   
			ll R=upper_bound(V[Type].begin(),V[Type].end(),node(A[i].r,0))-V[Type].begin()-1; 
			if(A[i].op==1)
			{
				while(V[Type][L-1].r>=A[i].l) L--;
				while(V[Type][R].l>A[i].r) R--;
				Blo.Add(Type,L,R,A[i].l,A[i].r,A[i].a);
			}
			else
			{
				while(V[Type][L].l<A[i].l) L++;
				while(V[Type][R].r>A[i].r) R--;
				Ans[i]+=Blo.Query(L,R,A[i].a);	
			}
		}
//		Blo.DEBUG(Type);puts("===");
	}
	for(ll i=1;i<=m;i++) if(A[i].op==2) printf("%lld\n",Ans[i]);
	return 0;
}
/*
西风吹老洞庭波，一夜湘君白发多。
醉后不知天在水，满船清梦压星河。

10 5
1 2 10 6
1 5 7 1
2 5 9 3
2 1 4 8
2 1 10 3
*/

天降之物

题解

\(~~~~\) 还是分块，先不考虑修改，我们可以怎么求答案呢？

\(~~~~\) 对于块内求答案，预处理块内两个数的距离最小值，显然可以 \(\mathcal{O(n\sqrt{n})}\) 完成。对于块间答案，那一定是前面块的最右的 \(x\) 和当前块的最左的 \(y\) 或者交换上一种情况中的 \(x,y\)，所以维护一个块每个数最左，最右的位置。

\(~~~~\) 直接用 map 维护值时间会炸，但是注意到一个块内最多 \(\sqrt{n}\) 种值，所以可以把每个块单独离散化来做，那么空间就开得下了。

\(~~~~\) 那么修改呢？我们分三种情况讨论：

若该块内没有 \(x\) ：那直接跑路了；
若该块内有 \(x\)：
- 若该块内无 \(y\)：那我们直接把原来 \(x\) 离散化后的值的对应改成对应 \(y\)。
- 若该块内有 \(y\): 此时我们直接暴力修改 \(x\) 相关的距离（即 \(x\) 的最左、最右和与 \(x\) 有关的块内最小距离），那为什么是对的呢？因为我们一次修改做 \(\mathcal{O(\sqrt{n})}\)，同时块内的数种类数 \(-1\) ，因此一个块最多做 \(\mathcal{O(\sqrt{n})}\) 次这样的暴力修改，那自然就对了。

\(~~~~\) 然后就做完了！

代码

\(~~~~\) 自己的代码还莫名其妙WA，先贴一个和我的很像的。

查看代码

#include<bits/stdc++.h>
using namespace std;
static char buf[1000000],*p1=buf,*p2=buf,obuf[1000000],*p3=obuf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
template<typename item>
inline void read(register item &x){
    x=0;register int f=1;register char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=f;
}
const int N=1e5+10,sq=255,nq=N/sq+10;
int n,q,blk,last,a[N],b[N],bl[nq],br[nq],bel[N],tp[nq];
int fir[N],sec[N],ind[N];
short inp[N][nq],ins[N][sq];
inline void init(int l,int r)
{
	int d=bel[l],p=l-1;
	vector<int>vec;
	for(int i=l;i<=r;i++) vec.push_back(a[i]);
	sort(vec.begin(),vec.end());
	vec.resize(unique(vec.begin(),vec.end())-vec.begin());
	tp[d]=vec.size();
	for(int i=l;i<=r;i++) b[i]=lower_bound(vec.begin(),vec.end(),a[i])-vec.begin()+1,ind[p+b[i]]=a[i],inp[a[i]][d]=b[i];
	for(int i=l;i<=r;i++) sec[p+b[i]]=i;
	for(int i=r;i>=l;i--) fir[p+b[i]]=i;
	for(int i=1;i<=tp[d];i++) memset(ins[p+i],64,sizeof(ins[p+i]));
	for(int i=l;i<=r;i++)
	{
		for(int j=i+1;j<=r;j++)
		{
			int A=min(b[i],b[j]),B=max(b[i],b[j]);
			ins[p+A][B]=min(ins[p+A][B],(short)(j-i));
		}
	}
		
}
inline void rebuild(int l,int r,int x,int y)
{
	int d=bel[l],p=l-1;
	int inpx=inp[x][d],inpy=inp[y][d];
	fir[p+inpy]=min(fir[p+inpy],fir[p+inpx]),sec[p+inpy]=max(sec[p+inpy],sec[p+inpx]);
	fir[p+inpx]=sec[p+inpx]=0,inp[x][d]=0;
	if(inpx>inpy)
	{
		for(int i=1;i<=inpy;i++) ins[p+i][inpy]=min(ins[p+i][inpy],ins[p+i][inpx]);
		for(int i=inpy+1;i<=inpx;i++) ins[p+inpy][i]=min(ins[p+inpy][i],ins[p+i][inpx]);
		for(int i=inpx+1;i<=tp[d];i++) ins[p+inpy][i]=min(ins[p+inpy][i],ins[p+inpx][i]);
	}
	else
	{
		for(int i=1;i<=inpx;i++) ins[p+i][inpy]=min(ins[p+i][inpy],ins[p+i][inpx]);
		for(int i=inpx+1;i<=inpy;i++) ins[p+i][inpy]=min(ins[p+i][inpy],ins[p+inpx][i]);
		for(int i=inpy;i<=tp[d];i++) ins[p+inpy][i]=min(ins[p+inpy][i],ins[p+inpx][i]);
	}
}
int main(){
	read(n);read(q);
	for(int i=1;i<=n;i++)read(a[i]);
	for(int i=1;i<=n;i+=sq){
		blk++;
		bl[blk]=i,br[blk]=min(i+sq-1,n);
		for(int j=bl[blk];j<=br[blk];j++)
			bel[j]=blk;
		init(bl[blk],br[blk]);
	}
	while(q--){
		int opt,x,y;
		read(opt);read(x);read(y);
		x^=last; y^=last;
		if(opt==2)
		{
			int ans=n+1,lasx=-1e9,lasy=-1e9;
			if(x==y)
			{
				for(int i=1;i<=blk;i++) if(inp[x][i]) ans=0;
				if(ans==n+1) puts("Ikaros"),last=0;
				else printf("%d\n",last=ans);
				continue;
			}
			for(int i=1;i<=blk;i++)
			{
				int inpx=0,inpy=0,p=bl[i]-1;
				if(inpx=inp[x][i]) ans=min(ans,fir[p+inpx]-lasy);
				if(inpy=inp[y][i]) ans=min(ans,fir[p+inpy]-lasx);
				if(inpx&&inpy) ans=min(ans,(int)ins[p+min(inpx,inpy)][max(inpx,inpy)]);
				if(inpx) lasx=sec[p+inpx];
				if(inpy) lasy=sec[p+inpy];
			}
			if(ans==n+1) puts("Ikaros"),last=0;
			else printf("%d\n",last=ans);
		}
		else
		{
			if(x==y) continue;
			for(int i=1;i<=blk;i++)
			{
				int t=inp[x][i],p=bl[i]-1;
				if(!t) continue;
				if(!inp[y][i]) ind[p+t]=y,inp[x][i]=0,inp[y][i]=t;
				else rebuild(bl[i],br[i],x,y);
			}
		}
	}
}

「Ynoi2018」未来日记

\(~~~~\) 咕，咕咕咕~

2023.1.29：分块

由乃打扑克

题解

\(~~~~\) 据说有道题叫：置身天上之森，那道题好像是这道题的强化，不知道可不可信。但是您可以往上翻一点点看看？

\(~~~~\) （其实带 \(\log\) 点名被卡了，但是可以看注释。）

代码

查看代码

#include <bits/stdc++.h>
using namespace std;
static char buf[1000000],*p1=buf,*p2=buf,obuf[1000000],*p3=obuf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
template<typename item> inline void read(register item &x){
    x=0;register int f=1;register char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=f;
}
static char cc[20];
template<typename item> inline void print(register item x){ 
	register int len=0;
	if(x<0)x=-x,putchar('-');
	while(x)cc[len++]=x%10+'0',x/=10;
	while(len--)putchar(cc[len]);
}
int arr[100005],brr[100005],crr[100005];
int belong[100005],L[320],R[320],Tag[320];
inline int check(int x,int l,int r)//返回 [l,r] 内<=x的数的个数 
{
	int res=0;
	for(int i=l;i<=R[belong[l]];i++) res+=(arr[i]+Tag[belong[l]]<=x);
	for(int i=belong[l]+1;i<=belong[r]-1;i++)
	{
		if(x<brr[L[i]]+Tag[i]) continue;
		if(brr[R[i]]+Tag[i]<=x) {res+=R[i]-L[i]+1;continue;}
		res+=upper_bound(brr+L[i],brr+R[i]+1,x-Tag[i])-brr-L[i];
	}
	for(int i=L[belong[r]];i<=r;i++) res+=(arr[i]+Tag[belong[r]]<=x);
	return res;
}
inline int Abs(int x){return x>=0?x:-x;}
int main() {
//	freopen("data.in","r",stdin);
//	freopen("my.out","w",stdout);
	int n,m;read(n);read(m);
	const int Siz=330;
	int Maxn=-1e9,Minn=1e9;
	for(int i=1;i<=n;i++)
	{
		read(arr[i]); brr[i]=arr[i];
		belong[i]=(i-1)/Siz+1;
		if(!L[belong[i]]) L[belong[i]]=i;
		R[belong[i]]=i;
		Maxn=max(Maxn,arr[i]); Minn=min(Minn,arr[i]); 
	}
	for(int i=1;i<=belong[n];i++) sort(brr+L[i],brr+R[i]+1);
	for(int qwq=1,op,l,r,k;qwq<=m;qwq++)
	{
		read(op);read(l);read(r);read(k);
		if(op==2)
		{
			if(k>0) Maxn+=k;
			if(k<0) Minn+=k;
			if(belong[l]==belong[r])
			{
				for(int i=l;i<=r;i++) arr[i]+=k;
				for(int i=L[belong[l]];i<=R[belong[l]];i++) brr[i]=arr[i];
				sort(brr+L[belong[l]],brr+R[belong[l]]+1);
			}
			else
			{
				for(int i=l;i<=R[belong[l]];i++) arr[i]+=k;
				for(int i=L[belong[l]];i<=R[belong[l]];i++) brr[i]=arr[i];
				sort(brr+L[belong[l]],brr+R[belong[l]]+1);
				
				for(int i=belong[l]+1;i<=belong[r]-1;i++) Tag[i]+=k;
				
				for(int i=L[belong[r]];i<=r;i++) arr[i]+=k;
				for(int i=L[belong[r]];i<=R[belong[r]];i++) brr[i]=arr[i];
				sort(brr+L[belong[r]],brr+R[belong[r]]+1);
			}
		}
		else
		{
			if(r-l+1<k) {print(-1);putchar('\n');continue;}
			if(belong[l]==belong[r])
			{
				for(int i=l;i<=r;i++) crr[i]=arr[i]+Tag[belong[l]];
				sort(crr+l,crr+r+1);
				print(crr[l+k-1]);putchar('\n');
			}
			else
			{
				int Le=Minn,Ri=Maxn,mid,Ans;
				while(Le<=Ri)
				{
					mid=(1ll*Le+Ri)>>1;
					if(check(mid,l,r)<k) Le=mid+1; //该数以内的<=k-1个 
					else Ri=mid-1,Ans=mid;
				}
				print(Ans);putchar('\n');
			}
		}
	}
	fwrite(obuf,p3-obuf,1,stdout);
	return 0;
}
/*
西风吹老洞庭波，一夜湘君白发多。
醉后不知天在水，满船清梦压星河。

自信 \Theta(m\sqrt{n}\log w\log \sqrt{n})

显然可以再优化，但我觉得这就是一种自信 

10 10
15 11 -18 12 6 9 14 -2 -10 6
1 2 3 1
2 2 4 -3
1 4 10 7
1 2 2 1
1 8 8 1
2 4 10 4
1 4 10 1
1 7 10 4
2 1 4 -5
1 1 8 4	

-18
14
8
-2
-6
18
8
*/

「Luogu P2137」Gty的妹子树

题解

\(~~~~\) 操作分块。

\(~~~~\) 还是考虑没有修改，那我们可以依据 dfs 序建一颗线段树，线段树维护这个 dfs序区间内的数排序过后的结果，往上合并就用归并排序，显然这样建树还是 \(\mathcal{O(n\log n)} 的\)，查询就直接对每个结点查完了做加法即可。

\(~~~~\) 那还是考虑加入了修改过后？显然即使第一种修改都不方便在线段树上做了，更不用说第二种会改形态的玩意了。所以我们操作分块：

\(~~~~\) 由于两种操作我们都可以简单地计算出它们对答案的影响，所以对于一定量（\(B\) 以内）的修改我们可以维护倍增数组方便判断祖先，然后直接扫描它们来计算新的答案。而当量超过 \(B\) 时，我们直接把操作做到树上然后整个重构线段树，那么就有 \(\mathcal{O(mB\log n+\frac{m}{B} n\log n)}\)，取 \(B=\sqrt{m}\) 即可。

\(~~~~\) 然后注意一堆细节。不过还好题目不卡常。

代码

查看代码

#include <bits/stdc++.h>
using namespace std;
template<typename T>void read(T &x)
{
    T sig=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')sig=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    x*=sig;
}
vector <int> G[60005];
int f[60005][18],lg[60005];
int siz[60005],dfn[60005],arr[60005],To[60005],Times,dep[60005];
void dfs(int u,int fa)
{
	f[u][0]=fa; dep[u]=dep[fa]+1;
	for(int i=1;i<=lg[dep[u]];i++) f[u][i]=f[f[u][i-1]][i-1];
	dfn[u]=++Times; siz[u]=1; To[Times]=u; 
	for(int i=0;i<(int)G[u].size();i++)
	{
		int v=G[u][i];
		if(v==fa) continue;
		dfs(v,u); siz[u]+=siz[v];
	}
}
void Clear(vector <int> &a){vector <int> b;swap(a,b);}
struct SegmentTree{
	#define ls p<<1
	#define rs p<<1|1
	#define lson p<<1,l,mid
	#define rson p<<1|1,mid+1,r
	vector <int> tr[240005];
	vector <int> Merge(vector <int> a,vector <int> b,vector <int> &res)
	{
		int i=0,j=0;
		while(i<(int)a.size()&&j<(int)b.size())
		{
			while(i<(int)a.size()&&a[i]<b[j]) res.push_back(a[i++]);
			while(j<(int)b.size()&&a[i]>=b[j]) res.push_back(b[j++]);
		}
		while(i<(int)a.size()) res.push_back(a[i++]);
		while(j<(int)b.size()) res.push_back(b[j++]);
		return res;
	}
	void pushUp(int p){Merge(tr[ls],tr[rs],tr[p]);}
	void Build(int p,int l,int r)
	{
		Clear(tr[p]);
		if(l==r){tr[p].push_back(arr[To[l]]);return;}
		int mid=(l+r)>>1;
		Build(lson); Build(rson);
		pushUp(p);
	}
	int Query(int p,int l,int r,int lx,int rx,int k)
	{
		if(lx<=l&&r<=rx) return tr[p].end()-upper_bound(tr[p].begin(),tr[p].end(),k);
		int mid=(l+r)>>1,Ans=0;
		if(lx<=mid) Ans+=Query(lson,lx,rx,k);
		if(mid<rx)  Ans+=Query(rson,lx,rx,k);
		return Ans;
	}
	#undef ls
	#undef rs
	#undef lson
	#undef rson
}Seg;
void Build(int n)
{
	Times=0; dfs(1,0);
	Seg.Build(1,1,n);
}
struct Ask{
	int op,u,x,id;
	Ask(){}
	Ask(int Op,int U,int X){op=Op,u=U,x=X;}
};
int Fa[60005],Tmp[60005];
void makeSet(int N){for(int i=1;i<=N;i++) Fa[i]=i;}
int  findSet(int x){return Fa[x]==x?x:Fa[x]=findSet(Fa[x]);}
vector <Ask> Now;
void Clear(vector <Ask> &a){vector <Ask> b;swap(a,b);}
bool IsAnc(int a,int b)
{
	if(dep[a]<dep[b]) return false;
	for(int i=lg[dep[a]];~i;i--) if(dep[f[a][i]]>=dep[b]) a=f[a][i];
	return a==b;
}
int main() {
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	int n,m;read(n);
	for(int i=1,u,v;i<n;i++)
	{
		read(u);read(v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for(int i=1;i<=60000;i++) lg[i]=lg[i>>1]+1;
	for(int i=1;i<=n;i++) read(arr[i]);
	int lst=0,N=n,B,NN=n;
	Build(n);
	read(m);
	makeSet(60000);
	B=sqrt(m);
	for(int qwq=1,op,u,x;qwq<=m;qwq++)
	{
		read(op);read(u);read(x);
		u^=lst; x^=lst;
		if(!op)
		{
			vector<int>res;
//			for(int i=0;i<res.size();i++) cerr<<res[i]<<"*";cerr<<endl;
			int Ans;
			if(u<=N) Ans=Seg.Query(1,1,N,dfn[u],dfn[u]+siz[u]-1,x);
			else Ans=0;
			for(int i=0;i<(int)Now.size();i++) if(Now[i].op==1) Tmp[Now[i].u]=arr[Now[i].u];
			for(int i=0;i<(int)Now.size();i++)
			{
				int Op=Now[i].op,U=Now[i].u,X=Now[i].x;
				if(Op==1)
				{
					if(IsAnc(U,u)) Ans-=(Tmp[U]>x),Ans+=(X>x);
					Tmp[U]=X;
				}
				else
				{
					if(IsAnc(Now[i].id,u)) Ans+=(X>x);
					Tmp[Now[i].id]=X;
				}
			}
			printf("%d\n",lst=Ans);
		}
		if(op==1) Now.push_back(Ask(op,u,x));
		if(op==2)
		{
			n++; dep[n]=dep[u]+1; f[n][0]=u;
			Now.push_back(Ask(op,u,x)); Now.back().id=n;
			int rt=findSet(u); if(rt!=Fa[n]) Fa[n]=rt;
			for(int i=1;i<=lg[dep[n]];i++) f[n][i]=f[f[n][i-1]][i-1];
		}
		if((int)Now.size()==B)
		{
			for(int i=0;i<(int)Now.size();i++)
			{
				int Op=Now[i].op,U=Now[i].u,X=Now[i].x;
				if(Op==1) arr[U]=X;
				else
				{
					N++;
					G[U].push_back(N); G[N].push_back(U);
					arr[N]=X;
				}
			}
			Build(NN=N); makeSet(60000); Clear(Now);
		}
	}
	return 0;
}
/*
西风吹老洞庭波，一夜湘君白发多。
醉后不知天在水，满船清梦压星河。
*/

「Luogu P3863」序列

题解

\(~~~~\) 做了一年了，忘了。

代码

查看代码

#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
ll arr[100005],Ans[100005],belong[100005],del[100005],Who[100005],L[100005],R[100005];
struct Ask{
	ll op,x,val,id;
	Ask(){}
	Ask(ll Op,ll X,ll Val,ll Id){op=Op,x=X,val=Val,id=Id;}
}Q[200005];
vector <ll> Blo[100005];
bool cmp(Ask x,Ask y){return x.x!=y.x?x.x<y.x:x.id<y.id;}
void Modify(ll l,ll r,ll val)
{
	ll bl=belong[l],br=belong[r];
	if(bl==br)
	{
		Blo[bl].clear();
		for(ll i=l;i<=r;i++) del[i]+=val;
		for(ll i=L[bl];i<=R[bl];i++) Blo[bl].push_back(del[i]);
		sort(Blo[bl].begin(),Blo[bl].end());
		return;
	}
	Blo[bl].clear(); Blo[br].clear();
	for(ll i=l;i<=R[bl];i++) del[i]+=val; for(ll i=L[br];i<=r;i++) del[i]+=val;
	for(ll i=L[bl];i<=R[bl];i++) Blo[bl].push_back(del[i]); for(ll i=L[br];i<=R[br];i++) Blo[br].push_back(del[i]);
	sort(Blo[bl].begin(),Blo[bl].end()); sort(Blo[br].begin(),Blo[br].end());
	for(ll i=bl+1;i<=br-1;i++) Who[i]+=val;
}
ll Query(ll l,ll r,ll val)
{
	ll ret=0,bl=belong[l],br=belong[r];
	if(bl==br) {for(ll i=l;i<=r;i++) ret+=(del[i]+Who[bl]>=val);return ret;}
	for(ll i=l;i<=R[bl];i++) ret+=(del[i]+Who[bl]>=val);
	for(ll i=L[br];i<=r;i++) ret+=(del[i]+Who[br]>=val);
	for(ll i=bl+1;i<=br-1;i++) {ll Tmp=lower_bound(Blo[i].begin(),Blo[i].end(),val-Who[i])-Blo[i].begin();ret+=Blo[i].size()-Tmp;}
	return ret;
}
int main() {
	ll n,m,cnt;
	scanf("%lld %lld",&n,&m);
	for(ll i=1;i<=n;i++) scanf("%lld",&arr[i]);
	for(ll i=1,op,l,r,x;i<=m;i++)
	{
		Ans[i]=-1;
		scanf("%lld",&op);
		if(op==1)
		{
			scanf("%lld %lld %lld",&l,&r,&x);
			Q[++cnt]=Ask(op,l,x,i);
			if(r+1<=n) Q[++cnt]=Ask(op,r+1,-x,i);
		}
		else
		{
			scanf("%lld %lld",&l,&x);
			Q[++cnt]=Ask(op,l,x,i);
		}
	}
	sort(Q+1,Q+1+cnt,cmp);
	m++;ll tot=sqrt(m),now=0;
	for(ll i=1;i<=m;i++)
	{
		Blo[(i-1)/tot+1].push_back(0);
		belong[i]=(i-1)/tot+1;
		if(!L[belong[i]]) L[belong[i]]=i;
		R[belong[i]]=i;
	}
	for(ll i=1;i<=cnt;i++)
	{
		if(now!=Q[i].x) Modify(1,m,arr[Q[i].x]-arr[now]),now=Q[i].x;
		if(Q[i].op==1) Modify(Q[i].id+1,m,Q[i].val);
		else Ans[Q[i].id]=Query(1,Q[i].id,Q[i].val);
	}
	for(ll i=1;i<m;i++) if(~Ans[i]) printf("%lld\n",Ans[i]);
	return 0;
}

「Ynoi2018」五彩斑斓的世界

\(~~~~\) 这个博主见人就贴不是炸弹王就是鸽子，听他发言我倾向于后者。等会哪个带刀好人去把他刀了。

「Ynoi2019」魔法少女网站

题解

\(~~~~\) 子区间都 \(\leq x\) ，那我们不难想到把所有 \(\leq x\) 的点的位置都置为 \(1\) ，其余都为 \(0\) ，那我们的连续长为 \(L\) 的 \(1\) 贡献为 \(\frac{L\times (L+1)}{2}\).

\(~~~~\) 我们把一个区间的信息记作：\((S,l,r,len)\) 表示区间的答案，最左边连续 \(1\) 数，最右边连续 \(1\) 数，区间长度，那我们可以做到 \(\mathcal{O(1)}\) 合并两个区间。

\(~~~~\) 我们可以暴力从左往右看每个位置是 \((1,1,1,1)\) 还是 \((0,0,0,1)\) 的区间然后一个个合到询问上，但显然这样不优。那我们序列分块，每个询问只处理当前块的贡献。然后对于一个询问：若在这个块内为散，则直接暴力合并这个块的部分；否则我们一起处理：把所有询问从小到大排序，那么我们移动询问时就会有一些 \(0\) 变成 \(1\) ，我们用双向链表来处理修改，同时维护好当前这个整块的上述信息。然后直接把询问的信息和这个块的答案合并即可。

\(~~~~\) 这样就是 \(\mathcal{O(n\sqrt n)}\) 的。为了维持复杂度，排序部分应使用基排。可以直接以 \(\sqrt{n}\) 为基数。

\(~~~~\) 另外也有对操作分块的,实现撤销影响，还是从小到大来处理询问，也是 \(\mathcal{O(n\sqrt{n})}\).

代码

查看代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T>void read(T &x)
{
    T f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
int n,m,siz,arr[300005],Copy[300005],ind[300005];
struct Query{
	int op,x,y,l,r,id;
}Q[300005];
struct node{
	int L,R,Len;ll Sum;
	node(){}
	node(ll S,int l,int r,int len){Sum=S;L=l,R=r,Len=len;}
}Ans[300005];
int B=560;
vector <int> buc[605],buc2[605],b;
node Merge(node aa,node bb){return node(aa.Sum+bb.Sum+1ll*aa.R*bb.L,aa.L+bb.L*(aa.Len==aa.L),bb.R+aa.R*(bb.Len==bb.R),aa.Len+bb.Len);}
bool cmp(int a,int bb){return arr[a]<arr[bb];}
int Pre[300005],Suf[300005];
ll CP[300005];
void Calc(int l,int r)
{
	for(int i=l;i<=r;i++) Pre[i]=i-1,Suf[i]=i+1;
	for(int i=0;i<B;i++)
	{
		for(int j=0;j<(int)buc[i].size();j++) buc2[Q[buc[i][j]].x/B].push_back(buc[i][j]);
		buc[i].clear();
	}
	for(int i=0;i<=n/B;i++)
	{
		for(int j=0;j<(int)buc2[i].size();j++) b.push_back(buc2[i][j]);
		buc2[i].clear();
	}
	if(b.empty()) return;
	int j=0;
	node res=node(0,0,0,r-l+1);//对排完的询问维护连续段 
	for(int i=l;i<=r;i++)
	{
		int k=ind[i];
		for(;j<(int)b.size()&&Q[b[j]].x<arr[k];j++) Ans[b[j]]=Merge(Ans[b[j]],res);
		if(j==(int)b.size()) break;
		if(Pre[k]==l-1) res.L+=Suf[k]-k;
		if(Suf[k]==r+1) res.R+=k-Pre[k];
		res.Sum+=1ll*(k-Pre[k])*(Suf[k]-k);
		Suf[Pre[k]]=Suf[k]; Pre[Suf[k]]=Pre[k];
	}
	for(;j<(int)b.size();j++) Ans[b[j]]=Merge(Ans[b[j]],res);
	b.clear();
}
void Solve(int l,int r)
{
	for(int i=l;i<=r;i++) arr[i]=Copy[i],ind[i]=i;
	sort(ind+l,ind+r+1,cmp);
	for(int i=1;i<=m;i++)
	{
		if(Q[i].op==1)
		{
			if(!(l<=Q[i].x&&Q[i].x<=r)) continue;
			Calc(l,r); arr[Q[i].x]=Q[i].y;
			for(int j=l;j<r;j++) if(arr[ind[j]]>arr[ind[j+1]]) swap(ind[j],ind[j+1]);
			for(int j=r;j>l;j--) if(arr[ind[j]]<arr[ind[j-1]]) swap(ind[j],ind[j-1]); 
		}
		else
		{
			int L=max(Q[i].l,l),R=min(Q[i].r,r),val=Q[i].x;
			if(l!=L||r!=R) 
				for(int j=L;j<=R;j++) 
					Ans[i]=Merge(Ans[i],arr[j]<=val?node(1,1,1,1):node(0,0,0,1));//边角 
			else buc[val%B].push_back(i);//满的，准备基排 
		}
	}
	Calc(l,r);
}
int main() {
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	read(n);read(m); //B=sqrt(n);
	for(int i=1;i<=n;i++) read(arr[i]),Copy[i]=arr[i],CP[i]=1ll*i*(i+1)/2;
	for(int i=1;i<=m;i++)
	{
		read(Q[i].op); Q[i].id=i;
		if(Q[i].op==1) read(Q[i].x),read(Q[i].y);
		else read(Q[i].l),read(Q[i].r),read(Q[i].x);
	}
	for(int l=1,r;l<=n;l=r+1) r=min(n,l+B-1),Solve(l,r);
	for(int i=1;i<=m;i++) if(Q[i].op==2) printf("%lld\n",Ans[i].Sum);
	return 0;
}
/*
西风吹老洞庭波，一夜湘君白发多。
醉后不知天在水，满船清梦压星河。

"这题调试难度中等偏下 " 你要不要看看你在说什么 
我为什么 1->0 的修改不能用双向链表维护前驱后继做到 O(1) 
为什么我非要询问分块了呢？ 
？？？ 

collapse collide 
*/

2023.1.30：数数

「AGC043D」 Merge Triplets

题解

\(~~~~\) 你有没有注意到 abracadabra 类似的东西：如果在原始块内递减的数归并（原始块没有排序），那新序列里面这些数也是递减紧挨着的，所以我们获得了一个新序列的必要条件：不存在长 \(\geq 4\) 的递减段。

\(~~~~\) 此外，一个块可以拆成：三个 \(1\) 的递减块；一个 \(1\)，一个 \(2\) 的递减块；一个 \(3\) 的递减块：所以一定有长为 \(1\) 的递减块比长为 \(2\) 的递减块多 \(3k（k\in \mathbb{N}）\) 个。

\(~~~~\) 注意到满足以上两个条件的序列必然可以构造合法的原序列，所以这两个条件就充要了。

\(~~~~\) 那么设计dp:\(dp_{i,j}\) 表示前 \(i\) 个数，长为 \(1\) 比长为 \(2\) 多 \(j\) 个的方案数。然后转移，同时乘上选递减数的系数即可。

代码

查看代码

#include <bits/stdc++.h>
using namespace std;
template<typename T>void read(T &x)
{
    T f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
int MOD;
inline int Add(int a,int b){return (a+b)%MOD;}
inline int Dec(int a,int b){return (a-b+MOD)%MOD;}
inline int Mul(int a,int b){return 1ll*a*b%MOD;}
inline int qpow(int a,int b)
{
	int ret=1;
	while(b)
	{
		if(b&1) ret=Mul(ret,a);
		b>>=1;a=Mul(a,a);
	}
	return ret;
}
const int Det=6000;
int dp[6005][12005];
int main() {
	int n;read(n);read(MOD);
	dp[0][0+Det]=1;
	for(int i=0;i<3*n;i++)
	{
		for(int j=-i;j<=i;j++)
		{
			dp[i+1][j+1+Det]=Add(dp[i+1][j+1+Det],dp[i][j+Det]);
			dp[i+2][j-1+Det]=Add(dp[i+2][j-1+Det],Mul(dp[i][j+Det],i+1));
			dp[i+3][j+Det]=Add(dp[i+3][j+Det],Mul(dp[i][j+Det],Mul(i+1,i+2)));
		}
	}
	int Ans=0;
	for(int j=0;j<=3*n;j++) Ans=Add(Ans,dp[3*n][j+Det]);
	printf("%d",Ans);
	return 0;
}
/*
西风吹老洞庭波，一夜湘君白发多。
醉后不知天在水，满船清梦压星河。

类似于 abracadabra 的套路可以发现递减的连续段一起放
那么就有形成的序列中递减的连续段长度 <=3
1-> 一个块拆成三个或者长1和2各一个
2-> 长1和2各一个
3-> 一整块
注意到还有一个必要条件是 ①>= ② 
还有条件吗 
*/

「AGC060C」Large Heap

题解

\(~~~~\) 放到树上考虑，那就是拓扑排序的时候 \(u\) 先比 \(v\) 访问的概率，那我们设现在在两颗深度 \(a,b\) 的树上先访问 \(u\) 的概率为 \(f_{a,b}\) ，在这种情况下先访问 \(a\) 那边的概率是 \(\frac{siz_u}{siz_u+siz_v}\) 因此可以列出转移：

\[f_{a,b}=\frac{siz_u}{siz_u+siz_v}f_{a-1,b}+(1-\frac{siz_u}{siz_u+siz_v})f_{a,b-1} \]

\(~~~~\) 直接dp即可：

代码

查看代码

#include <bits/stdc++.h>
using namespace std;
template<typename T>void read(T &x)
{
    T f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
const int MOD=998244353;
inline int Add(int a,int b){return (a+b)%MOD;}
inline int Dec(int a,int b){return (a-b+MOD)%MOD;}
inline int Mul(int a,int b){return 1ll*a*b%MOD;}
inline int qpow(int a,int b)
{
	int ret=1;
	while(b)
	{
		if(b&1) ret=Mul(ret,a);
		b>>=1; a=Mul(a,a);
	}
	return ret;
}
int Siz[5005],dp[5005][5005];
int main() {
	int n,A,B;
	read(n);read(A);read(B);
	A=n-A; B=n-B;
	Siz[0]=1;
	for(int i=1;i<=n;i++) Siz[i]=Mul(2,Siz[i-1]);
	for(int i=1;i<=n;i++) Siz[i]--,dp[A-1][i]=1;
	for(int i=A;i<n;i++)
	{
		for(int j=B;j<n;j++)
		{
			int P=Mul(Siz[i],qpow(Siz[i]+Siz[j],MOD-2));
			dp[i][j]=Add(Mul(dp[i-1][j],P),Mul(dp[i][j-1],Dec(1,P)));	
		}
	}
	printf("%d",dp[n-1][n-1]);
	return 0;
}

「AGC059C」 Guessing Permutation for as Long as Possible

题解

\(~~~~\) 首先先要读对题，那么这个时候把它放到无向图上，你就会明白题意要求给边定向使得任何一条边没有先被传递闭包。

\(~~~~\) 由于图是完全图，所以我们只需要考察大小为 \(3\) 的环。那么对于三个点 \((a,b,c)（a<b<c）\) ，假设 \((a,b),(b,c)\) 比 \((a,c)\) 先被提出，那一定不会有 \(a\rightarrow b \rightarrow c\)，否则 \((a,c)\) 就已经被定向了。也就是说 \(a\rightarrow b \Leftrightarrow b\leftarrow c\)，\(a \leftarrow b \Leftrightarrow b \rightarrow c\)。这明显是一个 \(\text{2-SAT}\) 问题。那么我们做并查集即可。

\(~~~~\) 最后我们数一数连通块个数，发现在不矛盾的前提下，当连通块个数为 \(a\) 时，我们就有 \(2^a\) 种定向方式，而每种定向最后也一定能唯一确定一种排列，所以答案就是 \(2^a\) 。

代码

查看代码

#include <bits/stdc++.h>
using namespace std;
template<typename T>void read(T &x)
{
    T f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
const int MOD=1e9+7;
inline int Add(int a,int b){return (a+b)%MOD;}
inline int Dec(int a,int b){return (a-b+MOD)%MOD;}
inline int Mul(int a,int b){return 1ll*a*b%MOD;}
inline int qpow(int a,int b)
{
	int ret=1;
	while(b)
	{
		if(b&1) ret=Mul(ret,a);
		b>>=1;a=Mul(a,a);
	}
	return ret;
}
bool vis[160025];
int id[405][405],fa[160025];
vector <int> G[160025];
int findSet(int x){return fa[x]==x?fa[x]:fa[x]=findSet(fa[x]);}
inline void AddEdge(int a,int b){int x=findSet(a),y=findSet(b);if(x!=y) fa[x]=y;}
inline int ID(int a,int b,int c){return (id[a][b]-1)*2+c;}
int main() {
	int n;read(n);
	for(int i=1,a,b;i<=n*(n-1)/2;i++)
	{
		read(a);read(b);
		if(a>b) swap(a,b);
		id[a][b]=i;
		fa[ID(a,b,1)]=ID(a,b,1); fa[ID(a,b,2)]=ID(a,b,2);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			for(int k=j+1;k<=n;k++)
			{
				int x=id[i][j],y=id[i][k],z=id[j][k];
				int Maxn=max(max(x,y),z);
				if(Maxn==x) 
					AddEdge(ID(i,k,1),ID(j,k,1)),AddEdge(ID(i,k,2),ID(j,k,2));
				if(Maxn==y) 
					AddEdge(ID(i,j,1),ID(j,k,2)),AddEdge(ID(i,j,2),ID(j,k,1));
				if(Maxn==z) 
					AddEdge(ID(i,j,1),ID(i,k,1)),AddEdge(ID(i,j,2),ID(i,k,2));
			}
		}
	}
	int Ans=0;
	for(int i=1;i<=n*(n-1)/2;i++) if(findSet(i*2-1)==findSet(i*2)) return puts("0")&0;
	for(int i=1;i<=n*(n-1);i++)
	{
		if(!vis[findSet(i)]) 
			vis[findSet(i)]=true,Ans++;	
	}
	Ans>>=1;
	if(!Ans) puts("0");
	else printf("%d",qpow(2,Ans));
	return 0;
}
/*
西风吹老洞庭波，一夜湘君白发多。
醉后不知天在水，满船清梦压星河。
*/

Yet Another ABC String

题解

\(~~~~\) 没完全看懂。那么半瓶水怎么能装满他人呢？

代码

查看代码

#include <bits/stdc++.h>
using namespace std;
template<typename T>void read(T &x)
{
    T f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
const int MOD=998244353;
inline int Add(int a,int b){return (a+b)%MOD;}
inline int Dec(int a,int b){return (a-b+MOD)%MOD;}
inline int Mul(int a,int b){return 1ll*a*b%MOD;}
inline int qpow(int a,int b)
{
	int ret=1;
	while(b)
	{
		if(b&1) ret=Mul(ret,a);
		b>>=1;a=Mul(a,a);
	}
	return ret;
}
int dp[3000005];
int Fac[3000005],Inv[3000005],Pow[3000005];
inline int C(int n,int r){return n>=r?Mul(Fac[n],Mul(Inv[r],Inv[n-r])):0;}
inline int CC(int a,int b,int c){return Mul(C(a+b+c,a),C(b+c,b));}
inline int Calc(int i,int x){return Mul(Pow[x>>1],C(i,x>>1));}
inline int Calcy(int i,int x){return i-(x>>1);}
int main() {
	int n,a,b,c;read(a);read(b);read(c); n=a+b+c;
	Fac[0]=1; for(int i=1;i<=n;i++) Fac[i]=Mul(Fac[i-1],i);
	Inv[n]=qpow(Fac[n],MOD-2); for(int i=n-1;i>=0;i--) Inv[i]=Mul(Inv[i+1],i+1);
	Pow[0]=1; for(int i=1;i<=n;i++) Pow[i]=Mul(Pow[i-1],MOD-2);
	
	for(int i=0;i<=n;i++)
	{
		if((n-i)&1) continue;
		int p=Calcy(i,n-i);
		if(p>=0) dp[p]=Add(dp[p],Calc(i,n-i));
	}
	for(int i=0;i<=n-3;i++)
	{
		if((n-3-i)&1) continue;
		int p=Calcy(i,n-3-i);
		if(p>=0) dp[p]=Dec(dp[p],Calc(i,n-3-i));
	}
	int Ans=0;
	for(int i=n;i>=0;i-=3) Ans=Add(Ans,Mul(dp[i],CC(a-(n-i)/3,b-(n-i)/3,c-(n-i)/3)));
	printf("%d",Ans);
	return 0;
}
/*
西风吹老洞庭波，一夜湘君白发多。
醉后不知天在水，满船清梦压星河。
*/

「AGC039E」 Pairing Points

题解

\(~~~~\) 我们先钦定从 \(1\) 连到了圆上的 \(i\) 点，那么事实上我们就把原问题划分成了 \([2,i)\) 和 \((i,n]\) 两个部分，也即两个部分都往外连一条边求答案。

\(~~~~\) 设dp状态：\(dp_{i,j,k}\) 表示区间 \([i,j]\) 内，\(k\) 向外连，其他都在区间内部连且合法的答案，此时其他线都必定会交 \(k\) 连出去的线。

\(~~~~\) 我们先枚举 \([2,i)\) 内 \(j\) 连出去到 \((i,n]\) 内某点，那么 \((j,i)\) 内的点都应该连出去要么和 \(j\) 交，要么和 \(i\) 交（否则要么没有线连这内部的，要么就连出环来），并且一定存在分界 \(p\) 使得 \((j,p]\) 都是和 \(j\) 交，\((p,i)\) 和 \(i\) 交，否则也会成环。那么我们就又形成了一个 \([2,j) \cup (j,p]\) 的子问题。右侧假设分界点为 \(q\) ，那同理也会有子问题。而 \(p\) 的右半部分和 \(q\) 的右半部分也是一个子问题。

\(~~~~\) 所以我们就有方程：

\[dp_{l,r,i} \leftarrow \sum dp_{p+1,q-1,i}\times dp_{l,p,j} \times dp_{q,r,k}\times [a_{j,k}=1] \]

\(~~~~\) 看一看是 \(\mathcal{O(n^7)}\) 的，能过，但还能优化。

\(~~~~\) 先枚举 \(p,q\) 再枚举 \(i\) :

\[dp_{l,r,i}\leftarrow dp_{p+1,q-1,i}\times \sum dp_{l,p,j} \times dp_{q,r,k} \times [a_{j,k}=1] \]

\(~~~~\) 后面的式子与 \(i\) 无关了，你就令 \(g_{l,p,k}=\sum f_{l,p,j}\times [a_{j,k}=1]\) ，把 \(g\) 一起转移然后就可以快速算 \(dp\) 了。

\(~~~~\) 做到 \(\mathcal{O(n^5)}\).

代码

查看代码

#include <bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
    T f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
    x*=f;
}
char Map[45][45];
ll f[45][45][45],g[45][45][45];
int main() {
    #ifndef ONLINE_JUDGE
    freopen("input","r",stdin);
    freopen("output","w",stdout);
    #endif
    int n;read(n);n*=2;
    for(int i=1;i<=n;i++) scanf("%s",Map[i]+1);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) Map[i][j]-='0';
    for(int i=2;i<=n;i++)
    {
        f[i][i][i]=1;
        for(int j=i+1;j<=n;j++) g[i][j][i]=Map[i][j];
    }
    for(int len=3;len<n;len+=2)
    {
        for(int l=2;l+len-1<=n;l++)
        {
            int r=l+len-1;
            for(int p=l;p<=r;p+=2)
            {
                for(int q=r;q>=l;q-=2)
                {
                    ll Tmp=0;
                    for(int k=q;k<=r;k++) Tmp+=g[l][k][p]*f[q][k][r];
                    for(int i=p+1;i<q;i++) f[l][i][r]+=f[p+1][i][q-1]*Tmp;
                }
            }
            for(int i=l;i<=r;i++)
                for(int j=i+1;j<=n;j++) g[l][j][r]+=Map[i][j]*f[l][i][r];
        }
    }
    ll Ans=0;
    for(int i=2;i<=n;i++) Ans+=Map[1][i]*f[2][i][n];
    printf("%lld",Ans);
    return 0;
}

鲜花

\(~~~~\) 今天对于 “思想倾轧”有点想法，但写了12道题解人萎了/kk.有时间再更或者看明天还记不记得住吧/kk.

标签：ch,int,ll,30,28,while,dep,2023.1,getchar
From： https://www.cnblogs.com/Azazel/p/17077346.html

2023.1.28~2023.1.30

一言(1.28)

2023.1.28:分块

「Ynoi Easy Round 2020」TEST_100

题解

代码

「POI2015」Odwiedziny

题解

代码

「Ynoi2014」置身天上之森

题解

代码

天降之物

题解

代码

「Ynoi2018」未来日记

2023.1.29：分块

由乃打扑克

题解

代码

「Luogu P2137」Gty的妹子树

题解

代码

「Luogu P3863」序列

题解

代码

「Ynoi2018」 五彩斑斓的世界

「Ynoi2019」魔法少女网站

题解

代码

2023.1.30：数数

「AGC043D」 Merge Triplets

题解

代码

「AGC060C」Large Heap

题解

代码

「AGC059C」 Guessing Permutation for as Long as Possible

题解

代码

Yet Another ABC String

题解

代码

「AGC039E」 Pairing Points

题解

代码

鲜花

相关文章

赞助商

阅读排行

「Ynoi2018」五彩斑斓的世界