Luogu4885 灭顶之灾

时间：2022-08-02 16:52:26

　　显然1的位置确定了整个矩阵，每一段连续的数即是对该位置的限制。化一下式子可以发现是一段区间或一段区间的补集，最后要求的是他们的交。看起来不太好求，于是转为求补集的并，那么排个序就完了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

ll read()

{

    ll x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

ll n,m,ans,mx,mn,pos;

int s,q,cnt=;

struct data

{

    ll x,y;

    bool operator <(const data&a) const

    {

        return x<a.x;

    }

}p[];

int main()

{

#ifndef ONLINE_JUDGE

    freopen("b.in","r",stdin);

    freopen("b.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

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

    while (s--)

    {

        ll a=(m+read()-)%m,b=(m+read()-)%m;

        if (a<b) cnt++,p[cnt].x=m-b,p[cnt].y=m-a-;

        else if (a>b)

        {

            cnt++,p[cnt].x=,p[cnt].y=m-a-;

            cnt++,p[cnt].x=m-b,p[cnt].y=m-;

        }

    }

    cnt++,p[cnt].x=m,p[cnt].y=m;

    sort(p+,p+cnt+);

    ll x=-;pos=-;

    for (int i=;i<=cnt;i++)

    if (p[i].x<=x+) x=max(x,p[i].y);

    else if (p[i].x-x==&&(pos==-)) pos=x+,x=p[i].y;

    else {cout<<"Uncertain!";return ;}

    if (pos==-) {cout<<"Impossible!";return ;}

    if (pos==) pos=m;

    while (q--)

    {

        ll x=read();

        if ((x+pos-)/m+<=n)

        ans^=(x+pos-)/m+^(x+pos-)%m+;

    }

    cout<<ans;

    return ;

}

相关文章