4722: 由乃
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 360 Solved: 131
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
20 20 152 3 26 133 54 79 81 72 109 66 91 82 100 35 23 104 17 51 114 12 58 2 1 17 2 6 12 1 1 12 2 3 5 2 11 11 2 7 19 2 6 15 1 5 12 1 1 9 1 10 19 2 3 19 2 6 20 2 1 13 2 1 15 2 1 9 1 1 1 2 1 7 2 7 19 2 6 19 2 3 6
Sample Output
Yuno
Yuno
Yuno
Yuno
Yuki
HINT
分析：
（话说这道题是道卡常题啊！！）
对于数据没有梯度这种东西，还是持有吐槽的态度的……还有常数太大，还好数据水。
好了，先说个题外话：当一个幼儿园有367个小朋友，那么肯定有两个人的生日会在同一天。
为什么要说这个呢？
因为这道题比如我们查询的区间长度为len，那么子区间方案数为2 ^ len，区间值域又为[len，（v + 1） * len]，只要使2 ^ len >（v + 1） * len,就一定存在有解的情况（原因如上述题外话）。
解方程：2 ^ len >（v + 1） * len ，解得len最小为 14.
所以只要查询区间长度 len > 13 就一定有解。
那么再来看看区间长度 <= 13的。题目让在大区间内，选两个互不相交的子集相等，可以转换成在大区间里每个数的系数有的为1（选入X集合），有的为0（不选），有的为 -1（选入Y集合）；
问是否存在使所有数加起来为0； 因为 2 ^ len 暴力枚举方案 len 是最大为13的，再乘上 m 显然时间是不够的。
我们可以采用二分的思想，先处理完[l，mid]区间。再处理[mid + 1，r]区间，这样 2 ^ 13被划为了 2 * (3 ^ 7），显然降低了很多。但常数还是巨大的（还好数据水）。
这样就处理完第一种查询了。
再来看第二种修改。
我们发现如果每次去乘常数也是巨大的，所以我们会联想到采用lazy标记。但是每次我们只询问叶子结点的值是多少，所以我们只用在询问叶子结点时才释放lazy标记。
再来看看具体操作 a[i] = （a[i]³）^ lazy，我们是不可能暴力去乘的，常数也是巨大的。貌似快速幂也常数大了点（因为调用了乘法，取模）。
我们发现无论再怎么次方，数都是在v以内的。我们可以预先处理出（0 ~ v - 1）的幂的表，这样每次就不用手动去乘了。
处理这个表类似于倍增的思想，我们知道每个数的data[i][j - 1]（表示i 的 2 ^ j - 1方的数是多少），就可以通过data[i][j] = data[data[i][j - 1]][j - 1]; 推出data[i][j]。O（nlogn）的预处理。
这样每次下方lazy标记变成了严格的log，而不是像快速幂一样在log上带上大常数。
然后操作一遍就可以了。
二分处理：
因为某G姓男子不懂二分这一块，我只好单独提出来解释一下：
比如说有13个数区间为[2，14]，mid 为 8，那么我们会分开处理[2,8]和[9,14]两段区间。
用dfs，枚举有的数系数为1，有的数系数为0，有的数系数为-1。比如说在[2,8]，[9,14]这些区间里就有数加减得0，我们是可以输出Yuno的。
没有的话看[2,8]里面出出现过的数是否[9,14]里面也出现过，出现过也可以输出Yuno。
话说某人问题是比如有5个数，999 3 7 4 16。如果我们会去处理[1,3]和[4，5]这两段区间，可是我们的X 和 Y集合是[2,4] 和[5]，[2,4]是跨越了mid的。是不会找到的。
我们这样想，如果在处理右区间[4,5]时，我们给[4]这里的数系数赋为-1，是不是就相当于加进了X集合。所以二分是可以处理的
AC代码：
# include <iostream> # include <cstdio> # include <cstring> # include <cstdlib> using namespace std; const int V = 1e3 + 10; const int N = 1e5 + 12; int read() { int ans = 0,f = 1; char i = getchar(); while(i < '0' || i > '9'){if(i == '-')f = -1;i = getchar();} while(i >= '0' && i <= '9'){ans = ans * 10 + i - '0';i = getchar();} return ans * f; } int n,m,v,mid,ol,x,y,d; int data[V][22],a[N],stack[N],cnt; int sum[N << 2],lazy[N << 2]; bool flag[N]; void down(int rt){ lazy[rt << 1] += lazy[rt]; lazy[rt << 1 | 1] += lazy[rt]; lazy[rt] = 0; } void push(int &ans,int &r){ int j = 20; while(j >= 0){ if(r >= (1 << j)){ ans = data[ans][j]; r -= (1 << j); if(r == 0)return; } j--; } } void updata(int L,int R,int l,int r,int rt){ if(L <= l && r <= R){ lazy[rt]++; return; } if(lazy[rt])down(rt); int mid = (l + r) >> 1; if(L <= mid)updata(L,R,l,mid,rt << 1); if(R > mid)updata(L,R,mid + 1,r,rt << 1 | 1); return; } void Query(int L,int l,int r,int rt){ if(l == r){ push(a[L],lazy[rt]); return; } if(lazy[rt])down(rt); int mid = (l + r) >> 1; if(L <= mid)Query(L,l,mid,rt << 1); else Query(L,mid + 1,r,rt << 1 | 1); return; } void init(){ for(int i = 0;i < v;i++){ data[i][0] = (i * i % v) * i % v; } for(int j = 1;j <= 20;j++){ for(int i = 0;i < v;i++){ data[i][j] = data[data[i][j - 1]][j - 1]; } } } void dfsl(int u,int dis,bool k){ if(ol)return; if(u == mid + 1){ if(k){ if(!dis){ ol = true; }else if(dis >= 0 && !flag[dis]){flag[dis] = true;stack[++cnt] = dis;} } return; } dfsl(u + 1,dis,k); dfsl(u + 1,dis + a[u] + 1,true); dfsl(u + 1,dis - a[u] - 1,true); return; } void dfsr(int u,int dis,bool k){ if(ol)return; if(u == y + 1){ if(k){ if(!dis){ ol = true; }else if(dis >= 0 && flag[dis]){ ol = true; } } return; } dfsr(u + 1,dis,k); dfsr(u + 1,dis + a[u] + 1,true); dfsr(u + 1,dis - a[u] - 1,true); return; } int main(){ n = read(),m = read(),v = read(); for(int i = 1;i <= n;i++){ a[i] = read(); } init(); for(int i = 1;i <= m;i++){ d = read(),x = read(),y = read(); if(d == 2){ updata(x,y,1,n,1); }else { if(y - x >= 13){ puts("Yuno"); }else { for(int j = x;j <= y;j++){ Query(j,1,n,1); } mid = (x + y) >> 1; ol = false;cnt = 0; dfsl(x,0,false); dfsr(mid + 1,0,false); for(int i = 1;i <= cnt;i++){ flag[stack[i]] = false; } if(ol)puts("Yuno");else puts("Yuki"); } } } return 0; }