「LOJ6277-6285」数列分块入门傻逼题

突然想起之前就想做的分块练习.

现在做起来真的感觉好傻逼啊.

分块暴力美学 有时候花里胡哨的数据结构出锅的时候也算是 一种补救方法吧.

分块代码不长也比较好写,根据hzwer的blog,分块时一定要想想这几个问题:

对于每次区间操作：

1.不完整的块 的$O(\sqrt{n})$个元素怎么处理?

2.$O(\sqrt{n})$个 整块 怎么处理?

3.要预处理什么信息（复杂度不能超过后面的操作）?

分块在大数据下很容易找出锅.

一般查错就分不同大小的块就好啦.

我贴完代码就跑!

分块入门1 区间加法 单点查值

没错 树状数组同学今天请你坐下！

//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
#define int long long
using namespace std;

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x * f;
}
const int MAXN = 5e4+10;
int sum_B[251],ref[MAXN],a[MAXN],n,m;
int refer_blk(int x){return (x-1)/m+1;}
///------------------head------------------
signed main(signed argc, char *argv[]){
    n=read();MM(sum_B,0);
    m=sqrt(n+0.5);
    rep(i,1,n) a[i]=read();
    rep(i,1,n){
        int opt=read(),l=read(),r=read(),c=read();
        if (opt) {printf("%lld\n",a[r]+sum_B[refer_blk(r)]);continue;}
        int L = refer_blk(l),R = refer_blk(r);
        if (L == R) {rep(j,l,r) a[j] += c; continue;}
        rep(j,L+1,R-1) sum_B[j] += c;
        rep(j,l,refer_blk(l)*m) a[j] += c;
        rep(j,(refer_blk(r)-1)*m+1,r) a[j] += c;
    }
	return 0;
}

分块入门2 区间加法 求区间小于c的元素个数

没错 树状数组同学您还是坐下吧

//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
using namespace std;
#define int long long

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x * f;
}
const int MAXN = 8e4+100;
const int MAXM = 500;
struct Blks{
    vector<int>v;
    int add;
    int query(int x){int q = lower_bound(v.begin(),v.end(),x-add)-v.begin();return q;}
}Blk[MAXM];
int n,a[MAXN],m,cnt=0,p=1,D;
int refer_blk(int x){return (x-1)/m+1;}
void Reset(int x){
    Blk[x].v.clear();
    rep(i,(x-1)*m+1,x*m) Blk[x].v.pb(a[i]);
    sort(Blk[x].v.begin(),Blk[x].v.end());
}
///------------------head------------------
signed main(signed argc, char *argv[]){
    n=read();D=n;
    m=sqrt(n);
    rep(i,1,n) {a[i]=read();Blk[refer_blk(i)].v.push_back(a[i]);}
    rep(i,1,m) sort(Blk[i].v.begin(),Blk[i].v.end());
    //rep(k,1,n) {for (auto it : Blk[k].v) printf("%lld ",it); puts("");}
    rep(ss,1,D){
        //printf("%lld\n",o);
        //rep(k,1,n) {for (auto it : Blk[k].v) printf("%lld ",it); puts("");}
        int opt,l,r,c;
        opt=read(),l=read(),r=read(),c=read();
        int L = refer_blk(l),R = refer_blk(r);
        if (opt) {
            int ret = 0;
            rep(i,l,min(m*L,r)) ret += (Blk[L].add + a[i] < c * c);
            if (L != R) rep(i,(R-1)*m+1,r) ret += (Blk[R].add + a[i] < c * c);
            rep(i,L+1,R-1) ret += Blk[i].query(c*c);
        //    cerr << l << " " << r << " " << c << endl;
            printf("%lld\n",ret);
        }
        else
        {
            rep(i,l,min(m*L,r)) a[i] += c;
            Reset(L);
            if (L != R) {rep(i,(R-1)*m+1,r) a[i] += c;Reset(R);}
            rep(i,L+1,R-1) Blk[i].add += c;
        }
    }
    return 0;
}

分块入门3 区间加法 查找前驱

//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
#define int long long
using namespace std;

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x * f;
}
const int MAXN = 1e5+10;
const int MAXM = 500+50;
//----------head----------
int n,M;
int v[MAXN],BL[MAXN],atag[MAXN];
set<int>Sets[MAXM];
void add(int a,int b,int c)
{
    for(int i=a;i<=min(BL[a]*M,b);i++)
    {
        Sets[BL[a]].erase(v[i]);
        v[i]+=c;
        Sets[BL[a]].insert(v[i]);
    }
    if(BL[a]!=BL[b])
    {
        for(int i=(BL[b]-1)*M+1;i<=b;i++)
        {
            Sets[BL[b]].erase(v[i]);
            v[i]+=c;
            Sets[BL[b]].insert(v[i]);
        }
    }
    for(int i=BL[a]+1;i<=BL[b]-1;i++)
        atag[i]+=c;
}
int query(int a,int b,int c)
{
    int Ret=-1;
    for(int i=a;i<=min(BL[a]*M,b);i++)
    {
        int val=v[i]+atag[BL[a]];
        if(val<c)Ret=max(val,Ret);
    }
    if(BL[a]!=BL[b])for(int i=(BL[b]-1)*M+1;i<=b;i++){int val=v[i]+atag[BL[b]];if(val<c)Ret=max(val,Ret);}
    for(int i=BL[a]+1;i<=BL[b]-1;i++){int x=c-atag[i];set<int>::iterator it=Sets[i].lower_bound(x);if(it==Sets[i].begin())continue;--it;Ret=max(Ret,*it+atag[i]);}
    return Ret;
}
signed main(signed argc, char *argv[])
{
    n=read();M=sqrt(n+0.5);
    for(int i=1;i<=n;i++)v[i]=read();
    for(int i=1;i<=n;i++)
    {
        BL[i]=(i-1)/M+1;
        Sets[BL[i]].insert(v[i]);
    }
    for(int i=1;i<=n;i++)
    {
        int f=read(),a=read(),b=read(),c=read();
        if(f==0)add(a,b,c);
        if(f==1)printf("%lld\n",query(a,b,c));
    }
    return 0;
}

分块入门4 区间加法 区间求和

其实多统计个sum信息就好了

//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define RG register
#define rep(i,a,b) for(RG int i=a;i<=b;i++)
#define per(i,a,b) for(RG int i=b;i>=a;i--)
#define fi first
#define se second
#define int long long
using namespace std;

inline char gc()
{
    static char now[1<<16],*S,*T;
    if(S==T) {T=(S=now)+fread(now,1,1<<16,stdin); if(S==T) return EOF;}
    return *S++;
}

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
	int x=0,f=1;char ch=gc();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=gc();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
	return x * f;
}

///------------------head------------------
const int MAXN = 8e4+100;
const int MAXM = 300+50;
int n,m,a[MAXN],add[MAXM],sum[MAXM];
inline int refer_blk(int x){return (x-1)/m+1;}

signed main(signed argc, char *argv[]){
    n=read(),m=sqrt(n+0.5);
    rep(i,1,n) a[i]=read(),sum[refer_blk(i)] += a[i];
    rep(op,1,n){
        int opt=read(),l=read(),r=read(),c=read();
        int L = refer_blk(l),R = refer_blk(r);
        if(!opt){
            rep(i,l,min(r,L*m)) a[i] += c,sum[L] += c;
            if (L != R) rep(i,(R-1)*m+1,r) a[i] += c,sum[R] += c;
            rep(i,L+1,R-1) add[i] += c;
        }
        else{
            int ret = 0;
            rep(i,l,min(r,L*m)) ret += a[i] + add[L];
            if (L != R) rep(i,(R-1)*m+1,r) ret += a[i] + add[R];
            rep(i,L+1,R-1) ret += sum[i] + m * add[i];
            printf("%lld\n",ret % (c+1));
        }
    }
	return 0;
}

分块入门5 区间开方 区间求和

就是利用一个数在有限次内(根据范围最多5~6次)一定可以被开方成1给整个块打标记

//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
#define int long long
using namespace std;

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x * f;
}

///------------------head------------------

const int MAXN = 8e4+100;
const int MAXM = 4e2+10;
int n,m,sum[MAXM],f[MAXM],a[MAXN];
inline int refer_blk(int x){return (x-1)/m+1;}
inline void Upd_in_blk(int x){
    if (f[x]) return ;
    f[x] = 1;
    sum[x] = 0;
    rep(i,(x-1)*m+1,x*m) {
        a[i] = sqrt(a[i] + 0.5);
        sum[x] += a[i];
        f[x] = a[i] > 1 ? 0 : f[x];
    }
}
signed main(signed argc, char *argv[]){
    n=read(),m=sqrt(n+0.5);
    rep(i,1,n) a[i]=read(),sum[refer_blk(i)] += a[i];
    rep(op,1,n){
        int opt=read(),l=read(),r=read(),c=read();
        int L=refer_blk(l),R=refer_blk(r);
        if(!opt){
            rep(i,l,min(r,L*m)) sum[L] -= a[i],a[i] = sqrt(a[i] + 0.5),sum[L] += a[i];
            if (L != R) rep(i,(R-1)*m+1,r) sum[R] -= a[i],a[i] = sqrt(a[i] + 0.5),sum[R] += a[i];
            rep(i,L+1,R-1) Upd_in_blk(i);
        }
        else{
            int ans = 0;
            rep(i,l,min(r,L*m)) ans += a[i];
            if(L != R) rep(i,(R-1)*m+1,r) ans += a[i];
            rep(i,L+1,R-1) ans += sum[i];
            printf("%lld\n",ans);
        }
    }
	return 0;
}

分块入门6 单点插入 单点求值

可以扔链表 但是分块我们可以资瓷更多的区间操作

本来的做法是找到新元素所在的块然后暴力向右移动

但是玩意所有操作都放在同一个块怎么办？

不难发现每次重构块是$O(n)$的

那么我们增加$\sqrt{n}$个元素就重构一次块 使得所有的块大小均衡

//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
#define int long long
using namespace std;

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x * f;
}

///------------------head------------------
const int MAXN = 1e5+100;
const int MAXM = 400+10;

int n,m,a[MAXN],M;
inline int refer_blk(int x){return (x-1)/M+1;}
vector<int>v[MAXM];
int buc[MAXN<<1],head = 0;
pair<int,int> query(int x){
    int xx = 1;
    while(x > v[xx].size()) x -= v[xx].size(),++xx;
    return make_pair(xx,x-1);
}
inline void Reset(void){
    head = 0;
    rep(i,1,m){
        for (auto j = v[i].begin(); j != v[i].end(); j++) buc[++head] = *j;
        v[i].clear();
    }
    int mm = sqrt(head);
    rep(i,1,head)
        v[(i-1)/mm+1].push_back(buc[i]);
    m=(head-1)/mm+1;
}
void ins(int x,int d){
    pair<int,int> t = query(x);
    int f1 = t.fi,f2 = t.se;
    v[f1].insert(v[f1].begin()+f2,d);
    if(v[f1].size() > 20 * M) Reset();
}//insert x to pos d
signed main(signed argc, char *argv[]){
    // freopen("a1.in","r",stdin);
    // freopen("my.out","w",stdout);
    n=read(),M=sqrt(n+0.5);
    rep(i,1,n) a[i]=read();
    rep(i,1,n) v[refer_blk(i)].pb(a[i]);
    m = (n - 1) / M + 1;
    rep(op,1,n){
        int opt = read(),l = read(),r = read(),c = read();
        if (!opt) {ins(l,r);}
        else {pair<int,int>t = query(r);int f1 = t.fi,f2 = t.se;printf("%lld\n",v[f1][f2]);}
    }
	return 0;
}

分块入门7 区间加法 区间乘法 单点询问

注意优先度就行

//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
#define int long long
using namespace std;

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x * f;
}
const int MAXN = 1e5+100;
const int MAXM = 400+50;
int n,m,a[MAXN],mul[MAXM],add[MAXM];
///------------------head------------------
const int Mod = 1e4+7;
inline int refer_blk(int x){return (x-1)/m+1;}
inline void Reset(int x){
    rep(i,(x-1)*m+1,min(x*m,n)) a[i]=(a[i]*mul[x]+add[x])%Mod;
    add[x] = 0; mul[x] = 1;
}
signed main(signed argc, char *argv[]){
    n=read(),m=sqrt(n+0.5);
    rep(i,1,n) a[i]=read();
    rep(i,1,refer_blk(n)) mul[i] = 1;
    rep(op,1,n){
        int opt=read(),l=read(),r=read(),c=read();
        int L = refer_blk(l),R = refer_blk(r);
        if (!opt) {
            Reset(L);
            rep(i,l,min(r,m*L)) a[i] += c,a[i] %= Mod;
            if (L != R) {Reset(R); rep(i,(R-1)*m+1,r) a[i] += c,a[i] %= Mod;}
            rep(i,L+1,R-1) {add[i] += c; add[i] %= Mod;}
        }
        else if (opt == 1){
            Reset(L);
            rep(i,l,min(r,m*L)) a[i] *= c,a[i] %= Mod;
            if (L != R) {Reset(R); rep(i,(R-1)*m+1,r) a[i] *= c,a[i] %= Mod;}
            rep(i,L+1,R-1) {add[i] *= c; add[i] %= Mod;mul[i] *= c;mul[i] %= Mod;}
        }
        else printf("%lld\n",(a[r]*mul[R]+add[R])%Mod);
    }
	return 0;
}

分块入门8 区间修改 区间询问

挺傻逼的.

//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
#define int long long
using namespace std;

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x * f;
}
const int MAXN = 1e5+100;
const int MAXM = 400+50;
int n,m,a[MAXN],f[MAXM];
///------------------head------------------
const int Mod = 1e4+7;
inline int refer_blk(int x){return (x-1)/m+1;}
inline void Reset(int x){
    if (f[x]==-1) return ;
    rep(i,(x-1)*m+1,min(x*m,n)) a[i]=f[x];
    f[x]=-1;
}
signed main(signed argc, char *argv[]){
    MM(f,-1);
    n=read(),m=sqrt(n+0.5);
    rep(i,1,n) a[i]=read();
    rep(op,1,n){
        int l=read(),r=read(),c=read();
        int L = refer_blk(l),R = refer_blk(r),ans = 0;
        Reset(L);
        rep(i,l,min(L*m,r)) {ans += a[i] == c; if (a[i] != c) a[i] = c;}
        if (L != R) {
            Reset(R);
            rep(i,(R-1)*m+1,r) {ans += a[i] == c; if (a[i] != c) a[i] = c;}
        }
        rep(i,L+1,R-1){
            if (f[i] != -1) {
                if (f[i] == c) ans += m;
                else f[i] = c;
            }
            else
            {
                rep(j,(i-1)*m+1,i*m){ans += a[j] == c; if(a[j] != c) a[j] = c;}
                f[i] = c;
            }
         }
         printf("%lld\n",ans);
    }
	return 0;
}

分块入门9 区间众数查询

离线版本不难想到

但似乎可以在线资瓷带修操作？

bzoj2724了解一下

//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define fi first
#define se second
#define int long long
using namespace std;

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x * f;
}

///------------------head------------------
const int MAXN = 1e5+10;
const int MAXM = 500+10;
int n,m,id,v[MAXN],f[MAXM][MAXM];
map<int,int>mp;
int val[MAXM],cnt[MAXM];
vector<int>ve[MAXM];
inline int refer_blk(int x){return (x-1)/m+1;}
void pre(int x)
{
    memset(cnt,0,sizeof(cnt));
    int mx=0,ans=0;
    for(int i=(x-1)*m+1;i<=n;i++)
    {
        cnt[v[i]]++;
        int t=refer_blk(i);
        if(cnt[v[i]]>mx||(cnt[v[i]]==mx&&val[v[i]]<val[ans]))
            ans=v[i],mx=cnt[v[i]];
        f[x][t]=ans;
    }
}
int query(int l,int r,int x)
{
    int t=upper_bound(ve[x].begin(),ve[x].end(),r)-lower_bound(ve[x].begin(),ve[x].end(),l);
    return t;
}
int query(int a,int b)
{
    int ans,mx;
    ans=f[refer_blk(a)+1][refer_blk(b)-1];
    mx=query(a,b,ans);
    for(int i=a;i<=min(refer_blk(a)*m,b);i++)
    {
        int t=query(a,b,v[i]);
        if(t>mx||(t==mx&&val[v[i]]<val[ans]))ans=v[i],mx=t;
    }
    if(refer_blk(a)!=refer_blk(b))
        for(int i=(refer_blk(b)-1)*m+1;i<=b;i++)
        {
            int t=query(a,b,v[i]);
            if(t>mx||(t==mx&&val[v[i]]<val[ans]))ans=v[i],mx=t;
        }
    return ans;
}
signed main(signed argc, char *argv[])
{
    n=read();m=sqrt(n+0.5);
    rep(i,1,n){v[i]=read();if(!mp[v[i]]){mp[v[i]]=++id;val[id]=v[i];}
        v[i]=mp[v[i]];ve[v[i]].push_back(i);
    };
    rep(i,1,refer_blk(n)) pre(i);
    rep(i,1,n){int a=read(),b=read();if(a>b)swap(a,b);printf("%lld\n",val[query(a,b)]);}
    return 0;
}