[acnoi2022] one step short

《 Curse 》

I also thought about , Write something 《 gossip 》 Class , However, considering the negative energy it must carry , And anticipating the headmaster and roll master —— Maybe there are dogs —— Pungent sarcasm in the comment area , Give up after all .

After all, I didn't write 《 gossip 》 Qualifications . I got good grades , So what he does is reasonable . I'm not like that . I have no right . I'm nothing .

The bottom of my heart is only cold 、 Darkness and death . My life is only worth cursing, not chatting . I can only name it 《 Curse 》 And there is nothing else .

But since then, this idea has been deeply rooted in my heart . Like an extinct volcano , Even if it is “ die ” Of , Its interior is still hot magma . So I borrow a little space in front of my blog , Write something a little .

Many incredible things have happened recently , And one after another ： First, the corneal plastic lens was accidentally lost , Then the braces were lost , Then the glasses leg of the frame glasses is broken , Now I'm at the bottom of the exam .

This seems to be some kind of omen . Something I don't want to admit , But there are already well-known omens .

but , Maybe , It's also a good thing . At least it makes my psychological burden less heavy .

I have turned a blind eye to my weakness . Don't be surprised at your incompetence . It's no surprise that I'm stupid .

---

subject

Background
because $\mathsf{OUYE}$ Excessive involution , Ordinary people like me have No, Existence Space 了 .

Title Description
consider $2^k$ A segment tree with leaves , The value of each node is the larger value of the child nodes .

The leaf value is $[1,2^k]$ Given the permutation . Now? $q$ Time to ask $x,y$, ask $x$ The maximum number of nodes on which the value can appear , If the exchange is at most $y$ The value of the secondary leaf .

Forced Online , And the space is limited $16\mathrm{MiB}$ .

Data range and tips
$k⩽19$ and $q⩽2\times 10^5$ .

Ideas

if $y\ne 0$, Then you only need to judge on a certain layer , Whether any node has at most $y$ More than $x$ Value .

$y=0$ The line segment tree does not change , You can count the answers directly . Therefore, the following is omitted .

Scan line

See greater than $x$, Consider processing from large to small $x$ .

Insert a new element one at a time , This will affect $k$ One node in each layer . Then we need to maintain each layer $\min cnt$ . Maintain with data structure , It seems to be $\mathcal{O}(k^2{2}^k)$ Complexity .

In fact, each layer of records $\min$ Number of occurrences of , Find out $\min$ After the change, the violence can be recalculated . Because there is $L$ In the layer of nodes ,$\min$ Not more than $\frac{2^k}{L}$, And each increase requires $\mathcal{O}(L)$ Recalculate , therefore $k$ The total complexity of the layer $\mathcal{O}(k{2}^k)$ .

So we get each $x$ Want to be in $t$ When it appears on nodes ,$y$ At least how much . If stored , You can deal with all inquiries online . Complexity $\mathcal{O}(k{2}^k+q\log k)$ . If online , Spatial complexity $\mathcal{O}(k{2}^k)$, If offline , Spatial complexity $\mathcal{O}(2^k+q)$ .

Two dimensional partial order

Scan line Is each $x$ To query the available segment tree nodes .

Think in reverse ： Each segment tree node can give $x$ What to offer .

Obviously the first $t$ Big value $v$ Limits are given ： if $x⩾v$, be $y⩾t-1$ You can get the answer of this interval .

Notice that there are only $\mathcal{O}(2^k)$ Such a contribution , Write down the answer directly with the array violence scan line .

The sum of this array and Scan line The results are the same .

Transforming dimensions

be aware Half plane in , The limits given $y⩾t-1$ Only $L$ Kind of , among $L$ Is the length of a single node .

So we record $f(t)$ by , stay $y⩾t-1$ when ,$x⩾f(t)$ Can reach this layer .

Due to the $f$ The length sum of is $\mathcal{O}(2^k)$, Space complexity is just $\mathcal{O}(2^k)$ Of .

Asking can still be divided , Time complexity $\mathcal{O}(k{2}^k+q\log k)$, Spatial complexity $\mathcal{O}(2^k)$ .

To be unique

How to force online ？ Use the previous answer .

However, the answer is only $k$ Kind of , So this $\mathcal{O}(qk)$ Ask offline , We also get acceptable practices .

Code

#include <cstdio>
#include <algorithm> // Almighty XJX yyds!!
#include <cstring> // oracle: ZXY yydBUS!!!
#include <cctype> // rainybunny root of the evil.
#include <functional>
using llong = long long;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
# define rep0(i,a,b) for(int i=(a); i!=(b); ++i)
inline int readint(){
    
    int a = 0, c = getchar(), f = 1;
    for(; !isdigit(c); c=getchar()) if(c == '-') f = -f;
    for(; isdigit(c); c=getchar()) a = a*10+(c^48);
    return a*f;
}

const int MAXK = 19;
int a[1<<MAXK]; int* tag[MAXK];
int ori[1<<MAXK]; /** for y = 0 */

const int INF = 0x3fffFFFF;
int tmp[1<<MAXK];
int main(){
    
    int n = readint(), k = readint(), typ = readint();
    rep0(i,0,n) a[i] = readint()-1;
    rep0(j,0,k){
     // merge for each layer
        tag[j] = new int[2<<j];
        std::fill_n(tag[j],2<<j,INF);
        int* l = a; int* r = a+(2<<j);
        for(; l!=a+n; r+=(2<<j)){
    
            int* const mid = l+(1<<j);
            ori[std::min(*l,*mid)] = j; // lose here
            std::merge(l,mid,mid,r,tmp,std::greater<int>());
            memcpy(l,tmp,(2<<j)<<2); // copy back
            for(int* i=tag[j]; l!=r; ++l,++i)
                *i = std::min(*i,*l); // corresponding
        }
    }
    ori[n-1] = k; // the final winner
    for(int q=readint(),x,y,ans=0; q; --q){
    
        x = readint(), y = readint();
        if(typ) x ^= ans, y ^= ans;
        if(!y){
     printf("%d\n",ans=ori[x-1]); continue; }
        int l = 31-__builtin_clz(y); /** smaller than @a y */
        int r = 31-__builtin_clz(x--); /** too big to replace */
        if(l > r){
     printf("%d\n",ans=r); continue; }
        while(l != r){
    
            const int mid = (l+r+1)>>1;
            if(tag[mid-1][y] <= x) // acceptable
                l = mid; else r = mid-1;
        }
        printf("%d\n",ans=r);
    }
    return 0;
}