【Ynoi2012】NOIP2016人生巅峰 | Mrsrz's blog

树状数组+倍增+数学(?)

题目大意：

给定一个数列 $a_{1..n}$，有两个操作：

1. 给定区间 $l,r$，要从这个区间里选出两个不相交的可重集合（不得为空），集合中 $a_i$ 的贡献为 $a_i+1$，问是否存在一种选法，使两个集合的贡献之和相等。
2. 给定区间 $l,r$，令区间内每个数变为它的立方，对 $v$ 取模。

题解：

发现 $v$ 非常小，而且这个区间立方操作一看就非常难维护，于是猜答案有某些性质。

这种题的话，一般区间长度很大时答案都是恒定的。考虑得出一个可以接受的上界。

令区间长度为 $t$，那么所有数的和不超过 $1000t$，而不同的选法为 $2^t$。因此，根据鸽巢（鸽子）定理，当 $2^t>1000t$ 时必然有解。解出来的 $t$ 在 $(13,14)$ 之间。故当 $t>13$ 时必然存在选法。这个上界已经很不错了。

那么我们只需考虑 $t\leq13$ 的情况即可。

这相当于一个背包问题，由于我们只需要判断是否存在方案，所以可以用bitset来解决这个问题。当插入一个新的数，转移到的方案中有已经存在的数的时候，那么说明存在解（不用考虑有交的情况，因为可以把相交的都在两边减去，而这样的做法显然不会使选的数的下标完全一样）。

bitset只需要开到 $\frac{1000t}2$ 即可。那么做一次的复杂度为 $O(\frac{500(r-l+1)}{\omega})$，且常数非常小，可以通过。

再考虑维护区间立方的操作。用树状数组维护每个数被立方了多少次，然后可以通过倍增的方法求出每个数变成了多少。这里每个操作的复杂度都是 $O(\log n)$。

最短的 Ynoi 无疑了，甚至不到 1KB

Code：

#include<iostream>
#include<bitset>
using namespace std;
const int N=1e5+5;
int n,m,md,F[17][1001];
int B[N],a[N];
inline void add(int i,int x){for(;i<=n;i+=i&-i)B[i]+=x;}
inline int ask(int i){int x=0;for(;i;i&=i-1)x+=B[i];return x;}
inline int jump(int x,int k){
    for(int i=16;~i;--i)
        if(k>>i&1)x=F[i][x];
    return x;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>md;
    for(int i=0;i<md;++i)
        F[0][i]=i*i*i%md;
    for(int i=1;i<17;++i)
        for(int j=0;j<md;++j)
            F[i][j]=F[i-1][F[i-1][j]];
    for(int i=1;i<=n;++i)cin>>a[i];
    while(m--){
        int op,l,r;
        cin>>op>>l>>r;
        if(op==2)add(l,1),add(r+1,-1);else{
            if(r-l+1>13)cout<<"Yuno\n";else{
                bitset<6001>b,c;
                b[0]=1;
                bool ok=0;
                for(int i=l;i<=r&&!ok;++i){
                    c=b<<(jump(a[i],ask(i))+1);
                    if((b&c).any())ok=1;
                    b|=c;
                }
                cout<<(ok?"Yuno":"Yuki")<<'\n';
            }
        }
    }
    return 0;
}