frac

frac

关注
发信
关注(28)粉丝(399)

APIO2019简要题解

Luogu P5444 [APIO2019]奇怪装置

看到这种题，我们肯定会想到\((x,y)\)一定有循环

我们要找到循环节的长度

推一下发现\(x\)的循环节长为\(\frac{AB}{B+1}\)。等一下，\(t\)是整数，所以循环节长为\(\frac{AB}{GCD(A,B+1)}\)

\(y\)的循环节长为\(B\)

所以\((x,y)\)的循环节长为\(lcm(\frac{AB}{GCD(A,B+1)},B)=\frac{AB}{GCD(A,B+1)}\)

对每个时间段对循环节长取模进行区间覆盖即可

代码（用了__int128）

#include <bits/stdc++.h>

#define N 1000005

#define ll long long

#define getchar nc

using namespace std;

inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

inline ll read()

{

    register ll x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

inline void write(register ll x)

{

    if(!x)putchar('0');if(x<0)x=-x,putchar('-');

    static int sta[20];register int tot=0;

    while(x)sta[tot++]=x%10,x/=10;

    while(tot)putchar(sta[--tot]+48);

}

inline ll Max(register ll a,register ll b)

{

	return a>b?a:b;

}

vector<pair<ll,ll> >v;

int n;

ll A,B;

int main()

{

	n=read(),A=read(),B=read();

	__int128 k=(__int128)A*B/__gcd(A,B+1);

	for(register int i=1;i<=n;++i)

	{

		ll l=read(),r=read();

		if(r-l+1>=k)

		{

			write((ll)k);

			return 0;

		}

		else

		{

			l%=k;

			r%=k;

			if(l<=r)

				v.push_back(make_pair(l,r));

			else

			{

				v.push_back(make_pair(l,(ll)k-1));

				v.push_back(make_pair(0ll,r));

			}

		}

	}

	sort(v.begin(),v.end());

	ll l=0,r=-1,ans=0;

	for(register int i=0;i<v.size();++i)

	{

		if(v[i].first<=r)

			r=Max(r,v[i].second);

		else

			ans+=r-l+1,l=v[i].first,r=v[i].second;

	}

	ans+=r-l+1;

	write(ans);

	return 0;

}

Luogu P5443 [APIO2019]桥梁

我们先考虑不带修改怎么做——珂以贪心地将桥的承受重量和车的重量从大到小排序，从大往小扫描车，用并查集维护边和答案

考虑有修改操作，我们珂以使用分块，设块的大小为\(blk\)

那么每个块中的修改操作不超过\(\frac{q}{blk}\)个

我们先把没有修改的边和所有询问的点像不带修一样从大到小排序，从大往小扫描车，对于每辆车，单独加入被修改的一些边，加入后通过并查集回退来撤销，所以并查集不能路径压缩，要按秩合并，处理完询问后要将原图更新，但是不能直接快排，新边要和原来已经有序的边进行合并排序，这个单块复杂度是\(O(m\alpha+\frac{n^2}{blk^2}\alpha+m)\)

我blk取的是\(\sqrt{n\log n}\)，所以总复杂度是\(O(m \sqrt{n\log n} \alpha)\)

#include <bits/stdc++.h>

#define M 100005

#define getchar nc

using namespace std;

inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

inline int read()

{

    register int x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

inline void write(register int x)

{

    if(!x)putchar('0');if(x<0)x=-x,putchar('-');

    static int sta[20];register int tot=0;

    while(x)sta[tot++]=x%10,x/=10;

    while(tot)putchar(sta[--tot]+48);

}

struct edge{

	int u,v,w,i;

}e[M],E[M],tmp[M];

bool operator < (edge a,edge b)

{

	return a.w!=b.w?a.w>b.w:a.i<b.i;

}

struct query{

	int id,t,b,r;

}q[M],tmp1[M],tmp2[M];

inline bool cmp(register query a,register query b)

{

	return a.b>b.b;

}

int fa[M],sz[M],top;

struct mste{

	int u,v;

}sta[M];

inline int getfa(register int x)

{

	return x==fa[x]?x:getfa(fa[x]);

}

inline void Merge(register int u,register int v)

{

	u=getfa(u);

	v=getfa(v);

	if(u==v)

		return;

	if(sz[u]<sz[v])

		u^=v^=u^=v;

	fa[v]=u;

	sz[u]+=sz[v];

	sta[++top]=(mste){u,v};

}

inline void cancel()

{

	int u=sta[top].u,v=sta[top].v;

	--top;

	fa[v]=v;

	sz[u]-=sz[v];

}

int n,m,Q,blk,tot,t1,t2,ans[M];

int vis[M],id[M],d[M];

inline void work()

{

	for(register int i=1;i<=m;++i)

		vis[i]=0;

	for(register int i=1;i<=n;++i)

		fa[i]=i,sz[i]=1;

	t1=t2=top=0;

	for(register int i=1;i<=tot;++i)

		if(q[i].t==1)

			vis[q[i].b]=1,tmp1[++t1]=q[i];

		else

			tmp2[++t2]=q[i];

	sort(tmp2+1,tmp2+1+t2,cmp);

	for(register int i=1;i<=m;++i)

		id[e[i].i]=i;

	for(register int i=1,p=1;i<=t2;++i)

	{

		while(p<=m&&e[p].w>=tmp2[i].b)

		{

			if(!vis[e[p].i])

				Merge(e[p].u,e[p].v);

			++p;

		}

		int lastop=top;

		for(register int j=1;j<=t1;++j)

			d[tmp1[j].b]=e[id[tmp1[j].b]].w;

		for(register int j=1;j<=t1;++j)

			if(tmp1[j].id<tmp2[i].id)

				d[tmp1[j].b]=tmp1[j].r;

		for(register int j=1;j<=t1;++j)

			if(d[tmp1[j].b]>=tmp2[i].b)

				Merge(e[id[tmp1[j].b]].u,e[id[tmp1[j].b]].v);

		ans[tmp2[i].id]=sz[getfa(tmp2[i].r)];

		while(top>lastop)

			cancel();

	}

	for(register int i=1;i<=t1;++i)

		e[id[tmp1[i].b]].w=tmp1[i].r;

	t1=t2=0;

	for(register int i=1;i<=m;++i)

		if(vis[e[i].i])

			E[++t1]=e[i];

		else

			e[++t2]=e[i];

	sort(E+1,E+1+t1);

	merge(E+1,E+1+t1,e+1,e+1+t2,tmp+1);

	for(register int i=1;i<=m;++i)

		e[i]=tmp[i];

}

int main()

{

	n=read(),m=read();

	blk=sqrt(n*log2(n));

	for(register int i=1;i<=m;++i)

		e[i].u=read(),e[i].v=read(),e[i].w=read(),e[i].i=i;

	sort(e+1,e+1+m);

	Q=read();

	for(register int i=1;i<=Q;++i)

	{

		int t=read();

		if(t==1)

		{

			int b=read(),r=read();

			q[++tot]=(query){i,t,b,r};

		}

		else

		{

			int s=read(),w=read();

			q[++tot]=(query){i,t,w,s};

		}

		if(tot==blk)

			work(),tot=0;

	}

	if(tot)

		work();

	for(register int i=1;i<=Q;++i)

		if(ans[i])

			write(ans[i]),puts("");

	return 0;

}

Luogu P5445 [APIO2019]路灯

这道题珂以暴力数据结构

我们用树状数组套主席树

每个点开个主席树，每个位置表示假如之后再也不修改，能到那个位置的次数（包括修改前的次数）

树状数组维护主席树的和

这样就珂以方便的进行差分

上代码（不想说了，自己看，简单易懂）

注意主席树中存的是之后再也不修改的答案数，要根据情况判断是否要减去一些

#include <bits/stdc++.h>

#define N 300005

#define getchar nc

using namespace std;

inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

inline int read()

{

    register int x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

inline void write(register int x)

{

    if(!x)putchar('0');if(x<0)x=-x,putchar('-');

    static int sta[20];register int tot=0;

    while(x)sta[tot++]=x%10,x/=10;

    while(tot)putchar(sta[--tot]+48);

}

int n,q,c[N];

set<int> st;

set<int>::iterator now,pre,nxt;

struct node{

	int ls,rs,val;

}tr[N*40];

int tot,rt[N];

inline void change(register int &x,register int l,register int r,register int pos,register int val)

{

	if(!x)

		x=++tot;

	tr[x].val+=val;

	if(l==r)

		return;

	int mid=l+r>>1;

	if(pos<=mid)

		change(tr[x].ls,l,mid,pos,val);

	else

		change(tr[x].rs,mid+1,r,pos,val);

}

inline int querys(register int x,register int l,register int r,register int L,register int R)

{

	if(!x)

		return 0;

	if(L<=l&&r<=R)

		return tr[x].val;

	int mid=l+r>>1,res=0;

	if(L<=mid)

		res+=querys(tr[x].ls,l,mid,L,R);

	if(R>mid)

		res+=querys(tr[x].rs,mid+1,r,L,R);

	return res;

}

inline int lowbit(register int x)

{

	return x&(-x);

}

inline void modify(register int x,register int pos,register int val)

{

	while(x<=n+1)

		change(rt[x],1,n+1,pos,val),x+=lowbit(x);

}

inline int query(register int x,register int pos)

{

	int res=0;

	while(x)

		res+=querys(rt[x],1,n+1,1,pos),x-=lowbit(x);

	return res;

}

int main()

{

	n=read(),q=read();

	for(register int i=1;i<=n;++i)

	{

		char ch=getchar();

		while(ch!='0'&&ch!='1')

			ch=getchar();

		c[i]=ch-'0';

	}

	st.insert(0),st.insert(n+1);

	modify(1,1,q);

	for(register int i=1,j=0;i<=n;++i)

	{

		if(c[i]==1)

			continue;

		st.insert(i);

		modify(j+1,i+1,-q);

		modify(i+1,i+1,q);

		j=i;

	}

	while(q--)

	{

		char ch=getchar();

		while(ch!='t'&&ch!='q')

			ch=getchar();

		if(ch=='t')

		{

			int x=read(),v=(c[x]==0)?1:-1;

			if(c[x]==1)

				st.insert(x);

			now=st.find(x);

			pre=nxt=now;

			--pre,++nxt;

			modify(*pre+1,x+1,q*v);

			modify(x+1,x+1,-q*v);

			if(*nxt!=n+1)

			{

				modify(*pre+1,*nxt+1,-q*v);

				modify(x+1,*nxt+1,q*v);

			}

			if(c[x]==0)

				st.erase(x);

			c[x]^=1;

		}

		else

		{

			int a=read(),b=read();

			write(query(a,b)-q*(st.lower_bound(a)==st.lower_bound(b))),puts("");

		}

	}

	return 0;

}
05-28 16:00
Powered by LMLPHP ©2024 frac 0.052271