【luoguP3792】由乃与大母神原型和偶像崇拜

这个题目……佛了。
有一个一定不会被hack但是我写不出来的做法,考虑离散化+插入中间空位里面不存在的数,这个时候查询区间max,min和后继的min就可以做到一定正确,但是这样会被卡空间……cnbb
然后我们考虑随机化贪心,考虑给每个权值随机一个数,然后查询区间的异或和是否和我们预处理的一样即可。

#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned long long ulo;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = gch()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = gch();
    if(b == 1)
        x = - x;
}

const int ms = 5e5 + 10;

int n, m, lx, ly, lz, a[ms], tmpa[ms << 2], ta;

ulo p[ms << 2], su1[ms << 2], su2[ms << 2], P[ms << 2];

mt19937 rnd(time(0));

struct node
{
    int opt, x, y;
}poi[ms];

inline int lowbit(int x)
{
    return x & (-x);
}

inline void change1(int x, ulo v)
{
    while(x <= n)
        su1[x] += v, x += lowbit(x);
}

inline void change2(int x, ulo v)
{
    while(x <= n)
        su2[x] ^= v, x += lowbit(x);
}

inline ulo ask1(int x)
{
    ulo rt = 0;
    while(x)
        rt += su1[x], x -= lowbit(x);
    return rt;
}

inline ulo ask2(int x)
{
    ulo rt = 0;
    while(x)
        rt ^= su2[x], x -= lowbit(x);
    return rt;
}

int main()
{
    re(n), re(m);
    for(ri i = 1; i <= n; i ++)
        re(a[i]), tmpa[++ ta] = a[i], tmpa[++ ta] = a[i] + 1;
    for(ri i = 1; i <= m; i ++)
    {
        re(lx), re(ly), re(lz), poi[i] = (node){lx, ly, lz};
        if(lx == 1)
            tmpa[++ ta] = lz, tmpa[++ ta] = lz + 1;
    }
    sort(tmpa + 1, tmpa + 1 + ta);
    ta = unique(tmpa + 1, tmpa + 1 + ta) - tmpa - 1;
    p[0] = time(0);
    for(ri i = 1; i <= ta; i ++)
        p[i] = rnd(), P[i] = p[i] ^ P[i - 1];
    for(ri i = 1; i <= n; i ++)
        a[i] = lower_bound(tmpa + 1, tmpa + 1 + ta, a[i]) - tmpa, change1(i, a[i]), change2(i, p[a[i]]);
    for(ri i = 1; i <= m; i ++)
        if(poi[i].opt == 1)
            poi[i].y = lower_bound(tmpa + 1, tmpa + 1 + ta, poi[i].y) - tmpa;
    for(ri i = 1; i <= m; i ++)
    {
        if(poi[i].opt == 1)
            change1(poi[i].x, poi[i].y - a[poi[i].x]), change2(poi[i].x, p[poi[i].y] ^ p[a[poi[i].x]]), a[poi[i].x] = poi[i].y;
        else
        {
            ulo mid; 
            int l, r;
            mid = (ask1(poi[i].y) - ask1(poi[i].x - 1)) / (poi[i].y - poi[i].x + 1);
            l = mid - (poi[i].y - poi[i].x) / 2;
            if ((poi[i].y - poi[i].x) & 1)
                r = mid + (poi[i].y - poi[i].x) / 2 + 1;
            else
                r = mid + (poi[i].y - poi[i].x) / 2;
            if(l <= 0 || r > ta)
                puts("yuanxing");
            else if((ask2(poi[i].y) ^ ask2(poi[i].x - 1)) == (P[r] ^ P[l - 1]))
                puts("damushen");
            else
                puts("yuanxing");
        }
    }
    system("pause");
}