自动搬运

查看原文

来自洛谷，原作者为

	JR_飘摇 这个家伙确实很懒，但至少知道他会爆0

搬运于2025-08-24 22:07:33，当前版本为作者最后更新于2018-12-27 15:42:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题解放这里吧！

当然也在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);
    }
}