题解 P4885 【灭顶之灾】

一扶苏一 · 2018-09-27 15:02:52 · 题解

推式子……瞎搞……想明白细节还是很恶心……~~果真是MDZZ~~

考虑对于每一个形如a,b在同一行的信息，都提供了一个a所能出现的区间。具体的，考虑在一列中，a最靠左能出现在第1行，最靠右能出现在第m-(b-a)行（此时b在第m行）。如果从左向右，从上向下数，设1前面有x个0，那么a是矩阵中第a+x个数。这就给出了我们一个方程：

(a+x)~Mod~m~\in~[1,m-b+a]

将a移项，化简可得：

x~Mod~M~\in~[1-a,m-b]

由此可以解出x的值。显然分别对于所有的信息解方程，最后留下的x就是x能取到的值。当这个值的个数为0时无解，大于1时有多组解（矩阵不唯一）

考虑对于每个解集如何求交。

由于是一个模意义下的解，x的解集共有两种情况，第一种情况形如x~\in~[l,r]，第二种情况形如x~\in~[0,l]~\bigcup~[r,m-1]。对于第一种情况显然可以直接对每个解集求交。考虑第二种情况，能否通过单独维护左右两个区间的交集，最后与第一种情况分别相交再取并集得到答案呢？事实上是不能的。考虑如图的解集：

其中解1、2、3分别是解不等式得到的解集区间。显然他们的交集是被红色区域框柱的一部分。如果对左右部分分别求交，得到的区间会是绿色线段。再与解3求交后求并的结果是空集。答案错误。

正确的姿势应该是对每个解维护补集的并集。最后对并集求补集，所有解的交集。如果您不能理解上面的话，请多读几遍画个图。维护答案的方法使用数组存储并集即可，然后按照左端点排序，扫描一遍数组，对于覆盖线段树数为0的区间累加ans即可得到答案。

对于目前的数据这样的代码交上去即可AC。但是需要注意的是这样的算法存在瑕疵。考虑下面的数据：

正确答案显然应该输出"Impossible!"

但事实上对于一部分代码这样的数据会输出一个答案3。输出x的解集你会发现计算机算出来的矩阵长这样：

0 1
2 3
4 5

这显然是不合法的，因为他的行数不合要求。但是我们在计算矩阵的时候并没有考虑行数的限制。解决方法很简单，对于所有一定出现在最后一行的数字（即b~\geq (n-1)~\times~m），对x的范围再做一个限制。具体的，设t=n~\times~m~-b，则一定不会有大于t个0出现，添加限制x~\leq~t即可。在代码中，因为我脑子有毛病，所以用了另一个计算这个限制的方法，十分脑残但是懒得改了= =。

由此计算出的x，便可作为正确的答案。

Code

在实现中，因为两个1e18相乘会爆long long，(n-1)~\times~m使用int128存储。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#ifdef ONLINE_JUDGE
#define putchar(a)\
puts("I am a cheater!");
#endif
#define rg register
#define ci const int
#define cl const long long int

typedef long long int ll;

namespace IO {
    char buf[90];
}

template<typename T>
inline void qr(T &x) {
    char ch=getchar(),lst=' ';
    while(ch>'9'||ch<'0') lst=ch,ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(lst=='-') x=-x;
}

template<typename T>
inline void write(T x,const char aft,const bool pt) {
    if(x<0) x=-x,putchar('-');
    int top=0;
    do {
        IO::buf[++top]=x%10+'0';
        x/=10;
    } while(x);
    while(top) putchar(IO::buf[top--]);
    if(pt) putchar(aft);
}

template<typename T>
inline T mmax(const T a,const T b) {if(a>b) return a;return b;}
template<typename T>
inline T mmin(const T a,const T b) {if(a<b) return a;return b;}
template<typename T>
inline T mabs(const T a) {if(a<0) return -a;return a;}

template<typename T>
inline void mswap(T &a,T &b) {
    T temp=a;a=b;b=temp;
}

const int maxn = 1000010;

struct Zay {
    ll x;int y;
    inline bool operator<(const Zay &_others) const {
        return this->x < _others.x;
    }
};
Zay MU[maxn];

ll n,m,ans,cnt;
int s,q;
__int128 uc,tp;

ll check();

int main() {
    qr(n);qr(m);qr(s);qr(q);
    rg ll a,b,l1=0,r1=m-1;
    uc=n-1;uc*=m;
    while(s--) {
        a=b=0;qr(a);qr(b);
        if((1.0*b)/n > (1.0*m)) {puts("Impossible!");return 0;}
        a%=m;
        ll tl=((1ll-a)%m+m)%m,tr=((m-b)%m+m)%m;
        if(tl <= tr) l1=mmax(l1,tl),r1=mmin(r1,tr);
        else {
            MU[++cnt]=(Zay) {tr+1,1};
            MU[++cnt]=(Zay) {tl-1,-1};
        }
        tp=b;
        if(tp > uc) {MU[++cnt]=(Zay) {m-(int)(tp-uc)+1,1};MU[++cnt]=(Zay) {m+1,-1};}
    }
    MU[++cnt]=(Zay) {-1,1};MU[++cnt]=(Zay) {l1-1,-1};MU[++cnt]=(Zay) {r1+1,1};MU[++cnt]=(Zay) {m+1,-1};
    rg ll k;
    std::sort(MU+1,MU+1+cnt);
    k=check();
    while(q--) {
        a=0;qr(a);
        a+=k;
        if((1.0*a/n) > 1.0*m) continue;
        ll _temp=(a-1)/m+1;ans^=_temp;
        _temp=(a-1)%m+1;
        ans^=_temp;
    }
    write(ans,'\n',true);
    return 0;
}

ll check() {
    rg ll k,sum=0,tg=0,i=1,tl=-2;
    while(i <= cnt) {
        if(tg <= 0) sum+=MU[i].x-1-tl,k=tl;
        tl=MU[i].x; 
        while((i <= cnt) && (MU[i].x == tl)) tg+=MU[i].y,++i;
    }
    if(!sum) {puts("Impossible!");exit(0);}
    else if(sum > 1) {puts("Uncertain!");exit(0);}
    else return k+1;
}

Summary

多个区间的交难以维护，可以考虑维护区间补集的并集，最后求补集即为交集。