2019暑假集训8.23（problem3.history）

发布时间：2020-12-14 05:09:00 所属栏目：大数据来源：网络整理

导读：题意：每次给的x，y都是错的，还原出来真正的应该是（x+c）%n和（y+c）%n 做法很多样，这里贴出Y学长的题解然鹅我应该就是那个遇到了评测机跑得很快的人吧！可持久化并查集过了耶。 ?如果满分算法的话我应该会选择打离线算法（但是我现在很懒不想打）贴

题意：

每次给的x，y都是错的，还原出来真正的应该是（x+c）%n和（y+c）%n

做法很多样，这里贴出Y学长的题解

然鹅我应该就是那个遇到了评测机跑得很快的人吧！可持久化并查集过了耶。

?如果满分算法的话我应该会选择打离线算法（但是我现在很懒不想打）贴出可持久化并查集的代码~

#include<bits/stdc++.h>
#define N 300002
using namespace std;
int read()
{
    int x=0,f=1;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();}
    return x*f;
}
int angry=0;
char s[3];
int c=0,n;
int fa2[N],ndnum=0;
int fa[N*20],lc[N*20],rc[N*20],root[N],dep[N*20];
void build(int k,int l,int r)
{
    if(l==r){fa[k]=l;return;}
    int mid=(l+r)>>1;
    build(lc[k]=++ndnum,l,mid);
    build(rc[k]=++ndnum,mid+1,r);
}
int query(int k,int L,int R,int pos)
{
    if(L==R) return k;
    int mid=(L+R)>>1;
    if(pos<=mid)return query(lc[k],L,mid,pos);
    else return query(rc[k],R,pos);
}
void merge(int last,int &k,int pos,int f)
{
    k=++ndnum;lc[k]=lc[last];rc[k]=rc[last];//复制 
    if(L==R)
    {
        fa[k]=f;
        dep[k]=dep[last];
        return;
    }
    int mid=(L+R)>>1;
    if(pos<=mid)merge(lc[last],lc[k],pos,f);
    else merge(rc[last],rc[k],f);
}
void update(int k,int pos)
{
    if(L==R){dep[k]++;return;}
    int mid=(L+R)>>1;
    if(pos<=mid)update(lc[k],pos);
    else update(rc[k],pos);
}
int get(int k,int x)
{
    int now=query(k,0,n-1,x);
    if(fa[now]==x)return now;
    return get(k,fa[now]);
}
int main()
{
    freopen("history.in","r",stdin);
    freopen("history.out","w",stdout);
    n=read();int T=read();
    int nian=0;
    build(root[0],n-1);
    
    for(int i=1;i<=T;++i)
    {
        scanf("%s",s);
        if(s[0]==‘K‘)angry=0,c=read();
        if(s[0]==‘R‘)
        {
            nian++;
            int x=read(),y=read(); 
            if(angry)x=(x+c)%n,y=(y+c)%n;
            root[nian]=root[nian-1];
            int posx=get(root[nian],x);
            int posy=get(root[nian],y);
            if(fa[posx]!=fa[posy])
            {
                if(dep[posx]>dep[posy])swap(posx,posy);
                merge(root[nian-1],root[nian],fa[posx],fa[posy]);
                if(dep[posx]==dep[posy])update(root[nian],fa[posy]);
            }
        }
        if(s[0]==‘T‘)
        {
            int st=read(),ed=read(),t=read();
            int f1=get(root[nian],st),f2=get(root[nian],ed);
            if(f1!=f2){angry=1;printf("Nn");continue;}
            f1=get(root[max(0,nian-t)],f2=get(root[max(0,ed);//小技巧max(0,nian-t) 
            if(fa[f1]==fa[f2])angry=1,printf("Nn");//上一次输出N那下一次就是生气的，输出Y那下一次就是不生气的 
            else angry=0,printf("Yn");
        }
        
    }
} 
/*
3 7
R 0 1
T 0 1 1
K 1
R 0 1
T 0 1 1
R 0 1
T 0 2 1

*/

View Code

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!