LOJ 510 - "libreoj noi round 1" memories outside the north school gate [line segment tree]

On the subject

Topic link :https://loj.ac/p/510

---

The main idea of the topic

Give me a code

function add(x,v)
    while x <= n do
        s[x] = s[x] xor v
        x = x + lowbit(x) // Be careful , Here is  lowbit, This is also the only difference between the two codes 
    end while
end function

function query(x)
    ans = 0
    while x > 0 do
        ans = ans xor s[x]
        x = x - lowbit(x)
    end while
    return ans
end function

among $\text{lowbit(x)}$ Express $x$ stay $K$ The value of the lowest non-zero position in hexadecimal .

Now give $n,q,K$,$q$ Secondary call $add(x,v)$ perhaps $query(x)$.

Require output each time $query(x)$ The value of the call .

$1\le n\le 10^9,2\le q,K\le 2\times 10^5$

---

Their thinking

Notice that we can do it one by one when asking , Mainly when modifying .

We first default that the lowest non-zero bit is a bit , Then it's equivalent to every time $x=x+x\%K$ until $x|K$, If only one bit is considered , It can also be regarded as every time $x=2x\%K$.

First of all, there are only two conditions for each number to reach it , One is $\frac{x}{2}$, The other is $\frac{x+K}{2}$, So if $K$ If it's an odd number , Exactly one of these two is an integer , That is, the entry side of each number is $1$, It's also out of the way $1$, So the final graph will definitely form several rings .

Then consider $K$ Not an odd number , If $x$ Of $2$ The number of qualitative factors shall not be less than $K$ Of , Then they can be expressed as $\frac{x}{2^p}$ and $\frac{K}{2^p}$, In this case $K$ It's odd again , It will also form a ring .

otherwise $x$ Multiply by two until the number of prime factors is not less than $K$, That is to say, this situation can't go beyond $\log K$ One step is bound to reach a ring or $0$.

So let's calculate the quantile first , Jump violently if the lowest position is not on the ring , Consider maintenance on the ring .

Now it's mainly about how to maintain the ring , On the same lowest position , For a modification $xy$（ One bit is $y$, The remaining bits are $x$）, Will affect an inquiry $x^{\prime }{y}^{\prime }$ Conditions .

We need to find a condition that is not about the bits of these points , Then we will consider defining a point for each ring as the ring head , Then all the operation queries are moved to the ring head .

Then we divide each modification into a section from the modified position to the ring head and a section from the ring head that keeps circling ,

Then one of the first restrictions is that the query position should be behind it and they all fall back to the same value behind the ring head , You can use the segment tree to maintain the positional relationship .

The second one first moves the inquiry upside down to the ring head , Then the limitation is that they are for The sum of carry times on the ring The remainder of is equal and the queried value is greater than the modified value , You can use the weight segment tree to maintain .

Time complexity ：$O(K{\log }^{2}n)$

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N=2e5+10,M=N<<7;
int n,q,K,cnt,lg[N],id[N],sum[N],noe[N],dis[N],len[N];
map<pair<int,int> ,int>rt[40],Rt[40];
map<int,int> g;
struct SegTree{
    
	int cnt,w[M],ls[M],rs[M];
	void Change(int &x,int L,int R,int pos,int val){
    
		if(pos<L||pos>R)return;
		if(!x)x=++cnt;w[x]^=val;
		if(L==R)return;int mid=(L+R)>>1;
		if(pos<=mid)Change(ls[x],L,mid,pos,val);
		else Change(rs[x],mid+1,R,pos,val);
		return;
	}
	int Ask(int x,int L,int R,int l,int r){
    
		r=min(r,R);l=max(l,L);
		if(l>r||!w[x])return 0;
		if(L==l&&R==r)return w[x];
		int mid=(L+R)>>1;
		if(r<=mid)return Ask(ls[x],L,mid,l,r);
		if(l>mid)return Ask(rs[x],mid+1,R,l,r);
		return Ask(ls[x],L,mid,l,mid)^Ask(rs[x],mid+1,R,mid+1,r);
	}
}T;
void dfs(int x,int pos,int one,int fr){
    
	if(id[x]){
    sum[fr]=one;return;}
	noe[x]=one;id[x]=fr;dis[x]=pos;len[fr]++;
	dfs(x*2%K,pos+1,one+(x*2>=K),fr);
	return;
}
int main()
{
    
	scanf("%d%d%d",&n,&q,&K);
	for(int i=1;i<=K;i++)
		if(i%2==0)lg[i]=lg[i/2]+1;
	for(int i=1;i<K;i++)
		if(lg[i]>=lg[K]&&!id[i])
			++cnt,dfs(i,0,0,cnt);
	while(q--){
    
		int op;scanf("%d",&op);
		if(op==1){
    
			int x,w,i=0,pw=1;
			scanf("%d%d",&x,&w);
			while(x*pw<=n){
    
				int p=x%K,y=x/K;
				while(p&&x*pw<=n){
    
					if(lg[p]>=lg[K]){
    
						T.Change(rt[i][mp(id[p],y-noe[p])],0,len[id[p]]-1,dis[p],w);
						T.Change(Rt[i][mp(id[p],(y-noe[p]+sum[id[p]])%sum[id[p]])],0,n/pw/K,y+sum[id[p]]-noe[p],w);
						x=0;break;
					}
					else g[x*pw]^=w,x+=x%K,p=x%K,y=x/K;
				}
				if(!x||x*pw>n)break;
				x=x/K;pw=pw*K;i++;
			}
		}
		else{
    
			int x;scanf("%d",&x);
			int i=0,pw=1,ans=0;
			while(x){
    
				int p=x%K,y=x/K;
				if(p!=0){
    
					if(lg[p]>=lg[K]){
    
						ans^=T.Ask(rt[i][mp(id[p],y-noe[p])],0,len[id[p]]-1,0,dis[p]);
						ans^=T.Ask(Rt[i][mp(id[p],(y-noe[p]+sum[id[p]])%sum[id[p]])],0,n/pw/K,0,y-noe[p]);
					}
					else ans^=g[x*pw];
				}
				x/=K;i++;pw=pw*K;
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}