题解 P5141 【列队】

· · 题解

题解放这里吧！

当然也在my blog里放了一份

吐槽ing：一道有趣的二进制题.

注意加粗部分是限制条件

我们先考虑暴力分40分：

首先那个Fight值一看就知道是二进制。

对于这个暴力分，应该是一种很暴力（废话）的解法，我们直接从b向a枚举，然后判断这一个数合不合法，如果合法，就+1，直到找到第k大，输出答案即可。

考虑100pts:

这里我们就要开始讨论二进制算法了。

首先我们考虑巨佬站队方式的限制，对于每个询问[a,b]，假设巨佬的Fight值是p，若p>b，那区间[b,p]就没有作用了，我们的查询区间就直接缩成了[a,min_{b,p-1}],这一个限制条件就解决了。

我们再考虑巨佬的站队对蒟蒻的约束作用（即限制了某些位必须是0）：

首先我们假设没有这个条件，很显然的，如果第i大的站队方式的Fight值是j，那么第i+1大的站队方式的Fight值就是j-1（二进制转十进制），

接着我们再考虑存在某些位必须是0的情况：

这里的方法是把所有有约束条件的0删去，得到一个新的，没有约束条件的数。

比如这里有一个第i大的数的二进制数，其中所有0都是被限制了的

1 0 1 0 1 0

我们把所有被限制的0删去，得到一个没有被限制的数：

1 1 1

显然这个Fight值是7，求第i+1大的数时，我们将7-1，得到6.

1 1 0

然后，我们再把刚才去掉的0加回去

1 0 1 0 0 0

这就是我们要找的数。

关于删除操作，我是这样做的，假设我们要删除下面这个二进制的第3个数：

1 1 1 1 1 1
      ^

我们先把后2位取下来：

1 1 1 1 0 0
s = 1 1

再删除第3位：

1 1 1 0 0 0

整体右移一位，在把s搬回去。

插入也是同理(改成左移)

具体代码实现（时间复杂度O(1)）：

void del(LL c)
{
    LL o = c - 1;
    s = ((((s & (~ c)) & (~ o)) >> 1) ^ (s & o));
}
void insert(LL c)
{
    LL o = c - 1;
    x = (((x & (~ o)) << 1) ^ (x & o));
}

然后还有一个问题就是，我们首先要找到满足[a,min_{b,p-1}]的最大值（知道了以后就可以解题了）。

我们同样先不考虑后面的限制，我们把min_{b,p-1}和p列出来从高位到低位枚举，假设蒟蒻的站队方式最大值为r，如果我们枚举到一位，满足这一位p是1，min_{b,p-1}也是1，由于约束，则蒟蒻的站队在这一位上必须是0，由于是从高位往低位枚举，则高位上肯定没有这种情况(否则就不会出现在这里了）,那r在这位上肯定是0，这时，可以发现，无论后面取什么数，其结果都比min_{b,p-1}小！那我们的r值就可以取到这位是0，后面都是1的情况。

对于其他情况，不难发现，我们必须要取min_{b,p-1}所在的值才能保证最大。

最后，找到了r后，我们去除限制条件，把所有巨佬所在值为1的权位上的值改为0，我们就找到了最大值。

代码也不长(甚至连数组都不用开)，但是如果没思路的话，代码不一定看得懂：

#include<cstdio>
#include<iostream>
#define LL unsigned long long
using namespace std;
LL n,m,t,q;
LL p,a,b,k,s,x;
void del(LL c)
{
    LL o = c - 1;
    s = ((((s & (~ c)) & (~ o)) >> 1ll) ^ (s & o));
}
void getmax()
{
    LL j = (1ll << (n - 1));
    for( ;j ; (j >>= 1))
      if((b & j) && (p & j)) break;
      if(!j) k = b;
      else k = ((b & (~ j)) | (j - 1));
    j = (1ll << (n - 1));
    for(; j; (j >>= 1))
      if(p & j) k = (k & (~ j));
    j = (1ll << (n - 1));s = k;
    for(; j; (j >>= 1))
      if((k & (~ (j - 1))) && (p & j)) del(j);
}
void insert(LL c)
{
    LL o = c - 1;
    x = (((x & (~ o)) << 1ll) ^ (x & o));
} 
int main()
{
    scanf("%lld%lld", &n,&m);
    for(LL i = 0;i<n;++i)
    {
        scanf("%lld", &t);
        p |= (t << i);
    }
    while(m --)
    {
        scanf("%lld%lld%lld",&a,&b,&q);
        b = min(p-1, b);
        getmax();
        x = s - q + 1;
        for(LL j = 1;j <= (1ll << n);j <<= 1)
          if(p & j) insert(j);
         if(x < a|| x>p) printf("POOR AFO!\n");
         else printf("%lld\n", x % 20031102);
    }
}