线段树总结（题目合集）

￡神魔★判官ぃ 2021-10-12 19:38 276阅读 0赞

## 1、POJ 3321 ##

## 题意：给出一个苹果树，每个节点一开始都有苹果。C X，如果X点有苹果，则拿掉，如果没有，则新长出一个。Q X，查询X点与它的所有后代分支一共有几个苹果。 ##

## 分析：利用dfs序将子树节点变成连续区间，然后利用线段树进行单点修改、区间求和就好了。注意vector<int> g\[N\]会超时，改成vector<vector<int> > g就好了。 ##

## 代码： ##

#include<cstdio>
    #include<vector>
    #include<cstdlib>
    using namespace std;
    const int N = 1e5+5;
    int n,m;
    int cnt,s[N],e[N];
    ///vector<int> g[N];（超时）
    vector<vector<int> > g(N);
    
    void dfs(int fa,int x) {
        s[x]=++cnt;
        for(int i=0;i<g[x].size();i++) {
            int u=g[x][i];
            if(u!=fa) dfs(x,u);
        }
        e[x]=cnt;
    }
    
    int sum[4*N];
    void bd(int o,int l,int r) {
        if(l==r) {
            sum[o]=1;
            return ;
        }
        int m=(l+r)/2;
        bd(2*o,l,m);
        bd(2*o+1,m+1,r);
        sum[o]=sum[2*o]+sum[2*o+1];
    }
    
    void up(int o,int l,int r,int x) {
        if(l==r) {
            sum[o]=1-sum[o];
            return ;
        }
        int m=(l+r)/2;
        if(x<=m) up(2*o,l,m,x);
        else up(2*o+1,m+1,r,x);
        sum[o]=sum[2*o]+sum[2*o+1];
    }
    
    int qu(int o,int l,int r,int ql,int qr) {
        if(ql<=l&&qr>=r) return sum[o];
        int m=(l+r)/2;
        if(qr<=m) return qu(2*o,l,m,ql,qr);
        else if(ql>m) return qu(2*o+1,m+1,r,ql,qr);
        else return qu(2*o,l,m,ql,qr)+qu(2*o+1,m+1,r,ql,qr);
    }
    
    int main() {
        scanf("%d",&n);
        for(int i=1;i<n;i++) {
            int u,v;
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(-1,1);
        bd(1,1,cnt);
        scanf("%d",&m);
        while(m--) {
            char op;
            int x;
            scanf(" %c%d",&op,&x);
            if(op=='C') up(1,1,cnt,s[x]);
            else printf("%d\n",qu(1,1,cnt,s[x],e[x]));
        }
        return 0;
    }

## 2、HDU  5306 ##

## 题意：给定a\[1...n\]，m次操作，0表示使\[L,R\]中的值a\[i\]=min(a\[i\],x)，1表示查最值，2表示查区间和。 ##

## 分析：jls的2016论文题，关键在于操作0如何剪枝，开始想到了如果区间最大值小于x，就可以不用向下更新了，但是剪枝力度不够，会超时，看了题解才知道还需要维护一个严格次大值，同时记录区间最大值出现的次数，分成三种情况，如果mx（最大值）<=x，直接返回；如果se（严格次大值）<=x&&x<mx，改变的只有最大值，将区间和减去最大值的个数\*（最大值-x）就可以了，打个懒惰标记，不再递归下去；如果x<se，暴力更新。可以证明复杂度为O（m\*log(n)）。推荐jls的论文——《区间最值操作与历史最值问题》。一直超时，lz标记int类型改成bool类型就过了。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define EF if(ch==EOF) return x;
    #define lc o<<1
    #define rc o<<1|1
    const int N=1e6+5;
    int T,n,m,a[N];
    ll mx[4*N],sum[4*N],se[4*N],cnt[4*N];
    bool lz[4*N];
    
    int read() {
        int x=0,f=1;register char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
        return x*f;
    }
    
    void pd(int o) {
        if(lz[o]) {
            if(mx[2*o]>mx[o]) {
                lz[2*o]=1;
                sum[2*o]-=cnt[2*o]*(mx[2*o]-mx[o]);
                mx[2*o]=mx[o];
            }
            if(mx[2*o+1]>mx[o]) {
                lz[2*o+1]=1;
                sum[2*o+1]-=cnt[2*o+1]*(mx[2*o+1]-mx[o]);
                mx[2*o+1]=mx[o];
            }
            lz[o]=0;
        }
    }
    
    void pu(int o) {
        mx[o]=max(mx[2*o],mx[2*o+1]);
        sum[o]=sum[2*o]+sum[2*o+1];
        if(mx[2*o]==mx[2*o+1]) se[o]=max(se[2*o],se[2*o+1]),cnt[o]=cnt[2*o]+cnt[2*o+1];
        else if(mx[2*o]>mx[2*o+1]) se[o]=max(se[2*o],mx[2*o+1]),cnt[o]=cnt[2*o];
        else se[o]=max(se[2*o+1],mx[2*o]),cnt[o]=cnt[2*o+1];
    }
    
    void bd(int o,int l,int r) {
        lz[o]=0;
        if(l==r) {
            mx[o]=sum[o]=a[l];
            se[o]=-1;
            cnt[o]=1;
            return ;
        }
        int m=(l+r)/2;
        bd(2*o,l,m);
        bd(2*o+1,m+1,r);
        pu(o);
    }
    
    void up(int o,int l,int r,int ql,int qr,int x) {
        if(mx[o]<=x)  return ;
        if(ql<=l&&qr>=r) {
            if(se[o]<x&&x<mx[o]) {
                lz[o]=1;
                sum[o]-=cnt[o]*(mx[o]-x);
                mx[o]=x;
                return ;
            }
        }
        pd(o);
        int m=(l+r)/2;
        if(qr<=m) up(2*o,l,m,ql,qr,x);
        else if(ql>m) up(2*o+1,m+1,r,ql,qr,x);
        else {
            up(2*o,l,m,ql,qr,x);
            up(2*o+1,m+1,r,ql,qr,x);
        }
        pu(o);
    }
    
    ll qumax(int o,int l,int r,int ql,int qr) {
        if(ql<=l&&qr>=r) return mx[o];
        pd(o);
        int m=(l+r)/2;
        if(qr<=m) return qumax(2*o,l,m,ql,qr);
        else if(ql>m) return qumax(2*o+1,m+1,r,ql,qr);
        else return max(qumax(2*o,l,m,ql,m),qumax(2*o+1,m+1,r,m+1,qr));
    }
    
    ll qusum(int o,int l,int r,int ql,int qr) {
        if(ql<=l&&qr>=r) return sum[o];
        pd(o);
        int m=(l+r)/2;
        if(qr<=m) return qusum(2*o,l,m,ql,qr);
        else if(ql>m) return qusum(2*o+1,m+1,r,ql,qr);
        else return qusum(2*o,l,m,ql,m)+qusum(2*o+1,m+1,r,m+1,qr);
    }
    
    int main() {
        T=read();
        while(T--) {
            n=read(),m=read();
            for(register int i=1;i<=n;i++) a[i]=read();
            bd(1,1,n);
            for(register int i=1;i<=m;i++) {
                int op,l,r,t;
                op=read(),l=read(),r=read();
                if(op==0) {
                    t=read();
                    up(1,1,n,l,r,t);
                }
                else if(op==1) printf("%lld\n",qumax(1,1,n,l,r));
                else printf("%lld\n",qusum(1,1,n,l,r));
            }
        }
        return 0;
    }

## 3、CodeForces - 438D ##

## 题意：给一个序列，3种操作。   1 u v 对于所有i u<=i<=v，输出a\[i\]的和   2 u v t 对于所有i u<=i<=v a\[i\]=a\[i\]%t   3 u v 表示a\[u\]=v（将v赋值给a\[u\]）   n,q<=1e5 a\[i\],t,v<=1e9 ##

## 分析：这个题时限长，数据也不是很大，普通的线段树加一个小剪枝就能过，主要来看操作二，我们维护一个区间最大值mx，如果mx<t，直接返回。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N=1e5+5;
    int n,m,a[N];
    ll mx[4*N],sum[4*N];
    
    void bd(int o,int l,int r) {
        if(l==r) {
            sum[o]=mx[o]=a[l];
            return ;
        }
        int m=(l+r)/2;
        bd(2*o,l,m);
        bd(2*o+1,m+1,r);
        mx[o]=max(mx[2*o],mx[2*o+1]);
        sum[o]=sum[2*o]+sum[2*o+1];
    }
    
    void upmod(int o,int l,int r,int ql,int qr,int x) {
        if(mx[o]<x) return ;
        if(l==r) {
            mx[o]%=x;
            sum[o]%=x;
            return ;
        }
        int m=(l+r)/2;
        if(ql<=m) upmod(2*o,l,m,ql,qr,x);
        if(qr>m) upmod(2*o+1,m+1,r,ql,qr,x);
        mx[o]=max(mx[2*o],mx[2*o+1]);
        sum[o]=sum[2*o]+sum[2*o+1];
    }
    
    void up(int o,int l,int r,int x,int v) {
        if(l==r) {
            mx[o]=sum[o]=v;
            return ;
        }
        int m=(l+r)/2;
        if(x<=m) up(2*o,l,m,x,v);
        else up(2*o+1,m+1,r,x,v);
        mx[o]=max(mx[2*o],mx[2*o+1]);
        sum[o]=sum[2*o]+sum[2*o+1];
    }
    
    ll qu(int o,int l,int r,int ql,int qr) {
        if(ql<=l&&qr>=r) return sum[o];
        int m=(l+r)/2;
        ll ans=0;
        if(ql<=m) ans += qu(2*o,l,m,ql,qr);
        if(qr>m) ans += qu(2*o+1,m+1,r,ql,qr);
        return ans;
    }
    
    int main() {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        bd(1,1,n);
        while(m--) {
            int op,l,r,x,k;
            scanf("%d",&op);
            if(op==1) {
                scanf("%d%d",&l,&r);
                printf("%lld\n",qu(1,1,n,l,r));
            }else if(op==2) {
                scanf("%d%d%d",&l,&r,&x);
                upmod(1,1,n,l,r,x);
            }else {
                scanf("%d%d",&k,&x);
                up(1,1,n,k,x);
            }
        }
        return 0;
    }

## 4、CodeForces - 920F ##

## 题意：给出一个数组，有两个操作，一个操作把区间所有数都变成其因子个数，另一个操作询问区间和。 ##

## 分析：容易知道，如果一个数<=2，那么操作一是无效的，我们可以预处理出每个数的因子个数，同时利用线段树维护区间最大值mx，如果mx<=2，那么直接返回。加了这个剪枝之后，复杂度是O（m\*log（n））的。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N=1e6+5;
    int n,m,a[N],d[N];
    ll mx[4*N],sum[4*N];
    vector<int> v[N];
    
    void bd(int o,int l,int r) {
        if(l==r) {
            sum[o]=mx[o]=a[l];
            return ;
        }
        int m=(l+r)/2;
        bd(2*o,l,m);
        bd(2*o+1,m+1,r);
        mx[o]=max(mx[2*o],mx[2*o+1]);
        sum[o]=sum[2*o]+sum[2*o+1];
    }
    
    void up(int o,int l,int r,int ql,int qr) {
        if(mx[o]<=2) return ;
        if(l==r) {
            mx[o]=sum[o]=d[mx[o]];
            return ;
        }
        int m=(l+r)/2;
        if(ql<=m) up(2*o,l,m,ql,qr);
        if(qr>m) up(2*o+1,m+1,r,ql,qr);
        mx[o]=max(mx[2*o],mx[2*o+1]);
        sum[o]=sum[2*o]+sum[2*o+1];
    }
    
    ll qu(int o,int l,int r,int ql,int qr) {
        if(ql<=l&&qr>=r) return sum[o];
        int m=(l+r)/2;
        ll ans=0;
        if(ql<=m) ans += qu(2*o,l,m,ql,qr);
        if(qr>m) ans += qu(2*o+1,m+1,r,ql,qr);
        return ans;
    }
    
    int main() {
        for(int i=1;i<N;i++)
            for(int j=i;j<N;j+=i)
                v[j].push_back(i);
        for(int i=1;i<N;i++) d[i]=v[i].size();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        bd(1,1,n);
        while(m--) {
            int op,l,r;
            scanf("%d",&op);
            if(op==1) {
                scanf("%d%d",&l,&r);
                up(1,1,n,l,r);
            }else {
                scanf("%d%d",&l,&r);
                printf("%lld\n",qu(1,1,n,l,r));
            }
        }
        return 0;
    }

## 5、hdu 3954 ##

## 题意：有N个英雄，每个英雄的初始等级为1，初始经验为0，有K个等级，QW个操作。接下来一行中有K-1个数值，代表升到等级2，等级3……所要达到的经验。接下来的QW行里，每行是一个操作，操作有两类，（1）"l r e"，代表区间\[l,r\]里的每个英雄将得到e乘以他的等级的经验。（2）"l r"，表示查询区间\[l,r\]里经验最大值。 ##

## 分析：因为我们只需要查询区间经验的最大值，所以我们只需要关注区间最大等级，因为最大等级的经验最大，如果最大等级不升级，用懒标记就行，否则更新到底。具体方法：sjmin存区间内升级需要的最少经验，djmax存区间内的最大等级，lz为惰性标记，如果没有英雄升级的话可以暂时不用把经验往下传，jymax存区间内的最大经验。而因为每个英雄的增加经验跟等级有关，所以sjmin的计算方法是用距离下一等级的经验除以当前等级，然后向上取整。因为k很小（升级次数很少），时间复杂度可以接受。 ##

## 总结：应该关注于题目所求，抓住主要特征，对这些询问有用的特征进行维护，**应该往什么时候区间内加的经验是一样的方向思考（适用于线段树的特征），考虑如何剪枝。** ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N = 1e4+5;
    int t,n,k,q,nd[N],djmax[4*N],jymax[4*N],sjmin[4*N],lz[4*N];
    ///sjmin存区间内升级需要的最少经验，djmax存区间内的最大等级，
    ///lz作为惰性标记，如果没有英雄升级的话可以暂时不用把经验往下传，
    ///jymax存区间内的最大经验。而因为每个英雄的增加经验跟等级有关，
    ///所以sjmin的计算方法是用距离下一等级（最大等级的下一级）的经验除以当前最大等级，然后向上取整。
    
    void pu(int o) {
        djmax[o]=max(djmax[2*o],djmax[2*o+1]);
        jymax[o]=max(jymax[2*o],jymax[2*o+1]);
        sjmin[o]=min(sjmin[2*o],sjmin[2*o+1]);
    }
    
    void pd(int o) {
        if(lz[o]) {
            lz[2*o]+=lz[o];
            jymax[2*o]+=djmax[2*o]*lz[o];
            sjmin[2*o]-=lz[o];
            lz[2*o+1]+=lz[o];
            jymax[2*o+1]+=djmax[2*o+1]*lz[o];
            sjmin[2*o+1]-=lz[o];
            lz[o]=0;
        }
    }
    
    void bd(int o,int l,int r) {
        djmax[o]=1;
        jymax[o]=0;
        sjmin[o]=nd[2];
        lz[o]=0;
        if(l==r) return ;
        int m=(l+r)/2;
        bd(2*o,l,m);
        bd(2*o+1,m+1,r);
    }
    
    void up(int o,int l,int r,int ql,int qr,int v) {
        if(ql<=l&&qr>=r) {
            if(v<sjmin[o]) {
                jymax[o] += djmax[o]*v;
                sjmin[o] -= v;
                lz[o] += v;
                return ;
            }else if(l==r) {
                jymax[o] += djmax[o]*v;
                while( jymax[o]>=nd[djmax[o]+1])
                    djmax[o]++;
                sjmin[o] = (nd[djmax[o]+1]-jymax[o])/djmax[o]+((nd[djmax[o]+1]-jymax[o])%djmax[o]!=0);
                return ;
            }
        }
        pd(o);
        int m=(l+r)/2;
        if(ql<=m) up(2*o,l,m,ql,qr,v);
        if(qr>m) up(2*o+1,m+1,r,ql,qr,v);
        pu(o);
    }
    
    int qu(int o,int l,int r,int ql,int qr) {
        if(ql<=l&&qr>=r) return jymax[o];
        pd(o);
        int m=(l+r)/2;
        int ans=0;
        if(ql<=m) ans=max(ans,qu(2*o,l,m,ql,qr));
        if(qr>m) ans=max(ans,qu(2*o+1,m+1,r,ql,qr));
        return ans;
    }
    
    int main(){
        scanf("%d",&t);
        for(int cas=1;cas<=t;cas++) {
            scanf("%d%d%d",&n,&k,&q);
            for(int i=2;i<=k;i++)
                scanf("%d",&nd[i]);
            nd[k+1]=2e9;
            bd(1,1,n);
            printf("Case %d:\n",cas);
            for(int i=1;i<=q;i++) {
                char op;
                int l,r,e;
                scanf(" %c",&op);
                if(op=='W') {
                    scanf("%d%d%d",&l,&r,&e);
                    up(1,1,n,l,r,e);
                }else {
                    scanf("%d%d",&l,&r);
                    printf("%d\n",qu(1,1,n,l,r));
                }
            }
            printf("\n");
        }
    	return 0;
    }

## 6、2018-2019 ACM-ICPC Brazil Subregional Programming Contest C. Pizza Cutter（逆序对） ##

## 题意：给你一个大小x\*y的披萨，横着切h刀，竖着切v刀，三刀不会交于一个点。 ##

## 分析：刚开始想复杂了，以为会有三线共点的情况出现，后面发现不用考虑这种情况，那这样就很好办了，统计交点个数就行，x、y方向每个点的贡献就是逆序对+1（将一端排序之后），x与y的交点的贡献就是（h+1）\*(v+1)，相加起来就是答案。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N = 1e5+5;
    int n,m,x,y,tp[N],tr[N];
    struct nd{
        int x,y;
    }a[N],b[N];
    
    bool cmp(nd p,nd q) {
        return p.x<q.x;
    }
    
    int lb(int x){
        return x&(-x);
    }
    
    void add(int x){
        while(x<N){
            tr[x]++;
            x+=lb(x);
        }
    }
    
    int qu(int x){
        int ans=0;
        while(x){
            ans+=tr[x];
            x-=lb(x);
        }
        return ans;
    }
    
    ll sv(nd c[],int n){
        sort(c+1,c+1+n,cmp);
        for(int i=1;i<=n;i++) tp[i]=c[i].y;
        memset(tr,0,sizeof(tr));
        sort(tp+1,tp+n+1);
        for(int i=1;i<=n;i++) c[i].y=lower_bound(tp+1,tp+1+n,c[i].y)-tp;
        ll ans=0;
        for(int i=1;i<=n;i++){
            add(c[i].y);
            ans+=i-qu(c[i].y);
        }
        return ans;
    }
    
    int main(){
        scanf("%d%d%d%d",&x,&y,&n,&m);
        for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
        ll ans=1LL*(n+1)*(m+1);
        ans += sv(a,n);
        for(int i=1;i<=m;i++) scanf("%d%d",&b[i].x,&b[i].y);
        ans += sv(b,m);
        printf("%lld\n",ans);
        return 0;
    }

## 7、HDU 6703 array ##

## 题意：给定一个长度为n的排列（1-n），要你实现操作两种，1 x：给第x个数加上1e7；2 l k：查询最小的且不小于k的且不在区间\[1,r\]里出现过的数。 ##

## 分析：一开始把题目理解错了，以为是在\[r+1,n\]区间里面找最小的大于等于k的数（还考虑了不存在的情况）。有两种思路，其实本质差不多的，一种比较直接的思路是建立权值线段树，维护权值区间内最右端的下标，然后去线段树上面找满足权值大于等于k的最右端点大于r的最优解（最小值）。暴力找回超时，考虑如何剪枝，就是在递归查询完左子树内存不存在大于r的下标之后，如果不存在，则先看一下右子树内的下标的最大值是否大于r。如果不大于r，则不必再进入右子树内查询，否则答案一定在右子树内。在进左子树之前也利用同样的判断条件来判断是否有必要进入左子树，这样做可以保证单次查询的复杂度是O(log n) 的。有点绕，结合代码更容易理解，对于操作一来说，直接修改对应权值的下标为无穷大，因为相当于把这个数删除了，只要有权值为这个值的数肯定满足条件。另外一种方法就是利用主席树求出\[r+1,n\]内大于等于k的最小值，对于操作一，相当于删除这个数，于是我们可以把这些值都存入set，去set里面找出大于等于k的最小值，然后再和主席树查询的结果取个最小值就是答案。具体的证明可以参考[https://blog.csdn.net/ccsu\_cat/article/details/100047649][https_blog.csdn.net_ccsu_cat_article_details_100047649]。两份代码其实差不多，因为主席树就是多颗权值线段树。 ##

## 代码一（权值线段树）： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N = 1e6+5;
    int t,n,m,a[N],idx[N],mx[4*N];
    
    void bd(int o,int l,int r) {
        if(l==r) {
            mx[o]=idx[l];
            return ;
        }
        int mid=(l+r)/2;
        bd(2*o,l,mid);
        bd(2*o+1,mid+1,r);
        mx[o]=max(mx[2*o],mx[2*o+1]);
    }
    
    void up(int o,int l,int r,int pos) {
        if(l==r) {
            mx[o] = N;
            return ;
        }
        int mid=(l+r)/2;
        if(pos<=mid) up(2*o,l,mid,pos);
        else up(2*o+1,mid+1,r,pos);
        mx[o] = max(mx[2*o],mx[2*o+1]);
    }
    
    int qu(int o,int l,int r,int R,int k) {
        if(l==r && mx[o] > R && k<=l) return l;
        int mid=(l+r)/2;
        if(k<=mid && mx[2*o] > R) {
            int ans = qu(2*o,l,mid,R,k);
            if( ans != n+1) return ans;
        }
        if(k<=r && mx[2*o+1] > R) {
            int ans = qu(2*o+1,mid+1,r,R,k);
            if( ans != n+1) return ans;
        }
        return n+1;
    }
    
    int main(){
        scanf("%d",&t);
        while(t--) {
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++) {
                scanf("%d",&a[i]);
                idx[a[i]]=i;
            }
            bd(1,1,n);
            int last=0;
            while(m--) {
                int op,x,y;
                scanf("%d",&op);
                if(op==1) {
                    scanf("%d",&x);
                    x^=last;
                    up(1,1,n,a[x]);
                }
                else {
                    scanf("%d%d",&x,&y);
                    x^=last,y^=last;
                    last = qu(1,1,n,x,y);
                    printf("%d\n",last);
                }
            }
        }
    	return 0;
    }

## 代码二（主席树）： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N = 1e5+5;
    int t,n,m,a[N];
    
    int rt[N*20],ls[N*20],rs[N*20],sum[N*20],cnt=0;
    void up(int pre,int& o,int l,int r,int pos) {
    	o=++cnt;
    	ls[o]=ls[pre];
    	rs[o]=rs[pre];
    	sum[o]=sum[pre]+1;
    	if(l==r) return ;
    	int m=(l+r)/2;
    	if(pos<=m) up(ls[pre],ls[o],l,m,pos);
    	else up(rs[pre],rs[o],m+1,r,pos);
    }
    
    int qu(int pre,int o,int l,int r,int k) {
        if(l==r && sum[o]-sum[pre] && k<=l) return l;
        int num = sum[ls[o]]-sum[ls[pre]],mid=(l+r)/2;
        if(k<=mid && num) {
            int ans = qu(ls[pre],ls[o],l,mid,k);
            if( ans != n+1) return ans;
        }
        num = sum[rs[o]]-sum[rs[pre]];
        if(k<=r && num) {
            int ans = qu(rs[pre],rs[o],mid+1,r,k);
            if( ans != n+1) return ans;
        }
        return n+1;
    }
    
    int main(){
        scanf("%d",&t);
        while(t--) {
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++)
                scanf("%d",&a[i]);
            cnt = 0;
            for(int i=1;i<=n;i++)
                up(rt[i-1],rt[i],1,n,a[i]);
            int last=0;
            set<int> st;
            while(m--) {
                int op,x,y;
                scanf("%d",&op);
                if(op==1) {
                    scanf("%d",&x);
                    x^=last;
                    st.insert(a[x]);
                }
                else {
                    scanf("%d%d",&x,&y);
                    x^=last,y^=last;
                    last = qu(rt[x],rt[n],1,n,y);
                    auto it = st.lower_bound(y);
                    if(it!=st.end()) last=min(last,*it);
                    printf("%d\n",last);
                }
            }
        }
    	return 0;
    }

## 8、Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2) D Restore Permutation ##

## 题意：给你n个数，每个数表示一个排列中前面小于它的数之和，要你还原这个排列。 ##

## 分析：1肯定是序列中最小值最右端的数，它对它后面的所有数都贡献了自身的值，我们把这个值减掉就好了，继续从小到大找出序列中最小值最右端的数的位置，利用线段树维护区间最小值，懒标记进行区间修改，如果右子树最小值小于等于左子树最小值，优先从右子树查找。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 1e6+5;
    ll n,s[N],ans[N],mi[4*N],lz[4*N],cnt,idx;
    
    void pd(int o) {
        if(lz[o]) {
            lz[2*o]+=lz[o];
            mi[2*o]-=lz[o];
            lz[2*o+1]+=lz[o];
            mi[2*o+1]-=lz[o];
            lz[o]=0;
        }
    }
    
    void bd(int o,int l,int r) {
        if(l==r) {
            mi[o]=s[l];
            return ;
        }
        int m=(l+r)/2;
        bd(2*o,l,m);
        bd(2*o+1,m+1,r);
        mi[o]=min(mi[2*o],mi[2*o+1]);
    }
    
    void up(int o,int l,int r,int ql,int qr) {
        if(ql<=l && qr>=r) {
            mi[o]-=cnt;
            lz[o]+=cnt;
            return ;
        }
        pd(o);
        int m=(l+r)/2;
        if(ql<=m) up(2*o,l,m,ql,qr);
        if(qr>m) up(2*o+1,m+1,r,ql,qr);
        mi[o]=min(mi[2*o],mi[2*o+1]);
    }
    
    void qu(int o,int l,int r) {
        if(l==r) {
            ans[l]=++cnt;
            idx=l;
            mi[o]=2e18;
            return ;
        }
        pd(o);
        int m=(l+r)/2;
        if(mi[2*o+1]<=mi[2*o]) qu(2*o+1,m+1,r);
        else qu(2*o,l,m);
        mi[o]=min(mi[2*o],mi[2*o+1]);
    }
    
    int main() {
        cin>>n;
    	for(int i=1;i<=n;i++) cin>>s[i];
    	s[n+1]=2e18;
    	bd(1,1,n+1);
    	for(int i=1;i<=n;i++) {
            qu(1,1,n+1);
            up(1,1,n+1,idx+1,n);
    	}
    	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
    	cout<<endl;
    	return 0;
    }

## 9、HDU 5875 Function ##

## 题意：给你一串数a再给你一些区间（l，r），求a\[l\]%a\[l+1\]...%a\[r\]。 ##

## 分析：可以发现a对b取模时：如果a<b,则等于原数，否则a会变小至少一半。就是说a最多成功取模log次，我们只需要在区间内找到最前面一个小于等于a的值就行，用线段树贪心找就好了，其实不需要找到这个值的位置，以为取模之后数会变小，在原来区间找就好了，更新左端点会更麻烦。 ##

## 我的代码（TLE了）： ##

///#include<bits/stdc++.h>
    #include<cstdio>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    #define ll long long
    const int N = 1e5+5;
    int a[N],mi[4*N];
    
    void bd(int o,int l,int r) {
        if(l==r) {
            mi[o] = a[l];
            return ;
        }
        int m=(l+r)>>1;
        bd(o<<1,l,m);
        bd(o<<1|1,m+1,r);
        mi[o] = min(mi[o<<1],mi[o<<1|1]);
    }
    
    int qu(int o,int l,int r,int ql,int qr,int val) {
        if(l==r) return mi[o];
        if(ql<=l && qr>=r) {
            int m = (l+r)>>1;
            if(mi[o<<1] <= val) return qu(o<<1,l,m,ql,qr,val);
            return qu(o<<1|1,m+1,r,ql,qr,val);
        }
        int m = (l+r)>>1;
        int ans=2e9;
        if(ql<=m) ans = qu(o<<1,l,m,ql,qr,val);
        if(ans<=val) return ans;
        if(qr>m) return qu(o<<1|1,m+1,r,ql,qr,val);
        ///return -1;
        return 2e9;
    }
    
    int main(){
        int t;
        while(~scanf("%d",&t)) {
            int n;
            scanf("%d",&n);
            for(int i=1;i<=n;i++) scanf("%d",&a[i]);
            bd(1,1,n);
            int q;
            scanf("%d",&q);
            while(q--) {
                int l,r,v;
                scanf("%d%d",&l,&r);
                if(l==r) {
                    printf("%d\n",a[l]);
                    continue;
                }
                v = a[l];
                while(1) {
                    int x = qu(1,1,n,l+1,r,v);
                    if(x>v)
                        break;
                    v%=x;
                    if(!v)
                        break;
                }
                printf("%d\n",v);
            }
        }
    	return 0;
    }

## AC代码： ##

#include<algorithm>
    #include<cstdio>
    using namespace std;
    const int N=1e5+5;
    int mi[N*4],a[N];
    void build(int l,int r,int root)
    {
        if(l==r)
        {
            mi[root]=a[l];
            return ;
        }
        int mid=l+r>>1;
        build(l,mid,root<<1);
        build(mid+1,r,root<<1|1);
        mi[root]=min(mi[root<<1],mi[root<<1|1]);
    }
    int query(int l,int r,int root,int ql,int qr,int val)
    {
        if(l==r)
            return mi[root];
        if(l>=ql&&r<=qr)
        {
            int mid=l+r>>1;
            if(mi[root<<1]<=val)
                return query(l,mid,root<<1,ql,qr,val);
            return query(mid+1,r,root<<1|1,ql,qr,val);
        }
        int mid=l+r>>1;
        int ans=2e9;
        if(mid>=ql)
            ans=query(l,mid,root<<1,ql,qr,val);
        if(ans<=val)
            return ans;
        if(mid<qr)
            return query(mid+1,r,root<<1|1,ql,qr,val);
        return 2e9;
    }
    int main()
    {
        int t;
        while(~scanf("%d",&t))
        {
            while(t--)
            {
                int n;
                scanf("%d",&n);
                for(int i=1;i<=n;i++)
                    scanf("%d",&a[i]);
                build(1,n,1);
                int q;
                scanf("%d",&q);
                while(q--)
                {
                    int l,r;
                    scanf("%d%d",&l,&r);
                    if(l==r||!a[l])
                        printf("%d\n",a[l]);
                    else
                    {
                        int v=a[l];
                        while(1)
                        {
                            int x=query(1,n,1,l+1,r,v);
                            if(x>v)
                                break;
                            v%=x;
                            if(!v)
                                break;
                        }
                        printf("%d\n",v);
                    }
                }
            }
        }
        return 0;
    }

## 10、HDU 5869 Different GCD Subarray Query ##

## 题意：给定一个a数组，每次询问一个区间\[l,r\]求这个区间内所有子区间的gcd的种类。 ##

## 分析：很套路的一道题，其他oj上有原题，和HDU3333（区间数的种类）思想差不多。线段树离线处理，这类做的不多，还不太熟练，还得找几个题做做。区间按右端点排序，一路扫过去，用map维护每个gcd现在所在的最右端点并不断向右更新，线段树维护到询问端点之前所有可能形成的gcd的最右位置。这类题得多做，熟能生巧。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define inf 0x3f3f3f3f
    const int N = 1e6+5;
    int n,Q,a[N],ans[N],sum[4*N];
    vector<pair<int,int> > v[N];
    map<int,int> mp;
    
    struct nd{
        int l,r,id;
    }q[N];
    bool cmp(nd u,nd v) {
        return u.r<v.r;
    }
    
    void bd(int o,int l,int r) {
        if( l==r ) {
            sum[o] = 0;
            return ;
        }
        int m=(l+r)/2;
        bd(2*o,l,m);
        bd(2*o+1,m+1,r);
        sum[o] = sum[2*o] + sum[2*o+1];
    }
    
    void up(int o,int l,int r,int p,int v) {
        if(l==r) {
            sum[o] += v;
            return ;
        }
        int m=(l+r)/2;
        if(p<=m) up(2*o,l,m,p,v);
        if(p>m) up(2*o+1,m+1,r,p,v);
        sum[o] = sum[2*o] + sum[2*o+1];
    }
    
    int qu(int o,int l,int r,int ql,int qr) {
        if(ql<=l&&qr>=r) return sum[o];
        int m=(l+r)/2,ans=0;
        if(ql<=m) ans += qu(2*o,l,m,ql,qr);
        if(qr>m) ans += qu(2*o+1,m+1,r,ql,qr);
        return ans;
    }
    
    int main(){
        while(~scanf("%d%d",&n,&Q)) {
            mp.clear();
            for(int i=1;i<=n;i++) v[i].clear();
            for(int i=1;i<=n;i++) scanf("%d",&a[i]);
            for(int i=1;i<=Q;i++)
                scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
            sort(q+1,q+1+Q,cmp);
            for(int i=1;i<=n;i++) {
                v[i].push_back({a[i],i});
                int x = a[i];
                for(int j=0;j<v[i-1].size();j++) {
                    int k = __gcd(a[i],v[i-1][j].first);
                    if(x != k) {
                        v[i].push_back({k,v[i-1][j].second});
                        x = k;
                    }
                }
            }
            bd(1,1,n);
            int j = 1;
            for(int i=1;i<=Q;i++) {
                while(j <= q[i].r) {
                    for(int k=0;k<v[j].size();k++) {
                        if( mp[v[j][k].first] ) {
                            up(1,1,n,mp[v[j][k].first],-1);
                        }
                        up(1,1,n,v[j][k].second,1);
                        mp[v[j][k].first] = v[j][k].second;
                    }
                    j++;
                }
                ans[q[i].id] = qu(1,1,n,q[i].l,q[i].r);
            }
            for(int i=1;i<=Q;i++)
                printf("%d\n",ans[i]);
        }
    	return 0;
    }

## 11、CodeForces 1187D Subarray Sorting ##

## 题意：对a数组任意区间排序，问是否能变成b数组。 ##

## 分析：很好的一道线段树+思维的题，最近这种线段树维护最值加思维出的比较多。开始想着找出b数组连续上升的区间，然后对a数组相应区间排序看是否相等，后面举出反例了。后面看了题解，我们来看这个样例: ##

## a: 15 9 7 10 8 ##

## b: 7 8 9 15 10 ##

## 对于操作a数组, 很明显第一步我们要把7挪到第一个位置,能把7挪到第一个位置的条件是区间\[1,3\]的最小值等于7,于是我们用线段树(线段树维护a数组)查询\[1,3\]的最小值即可. 第二步,我们要把8放到第二个位置,同理,\[1,5\]的最小值应该等于8,但是现在查询出来最小值等于7,但其实7已经放到第一个位置了,8的移动不应该被7影响.其实我们在移动完7之后,把7所在的位置的值设置为inf就好了,这样已经排好的7对8的移动就不会再产生影响了。参考[https://blog.csdn.net/Frozensmile/article/details/94366486][https_blog.csdn.net_Frozensmile_article_details_94366486]。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define inf 0x3f3f3f3f
    const int N = 1e6+5;
    int t,n,a[N],b[N],pos[N],mi[4*N];
    vector<int> va[N],vb[N];
    
    void bd(int o,int l,int r) {
        if(l==r) {
            mi[o] = a[l];
            return ;
        }
        int m=(l+r)/2;
        bd(2*o,l,m);
        bd(2*o+1,m+1,r);
        mi[o] = min(mi[2*o],mi[2*o+1]);
    }
    
    void up(int o,int l,int r,int p,int v) {
        if(l == r) {
            mi[o] = v;
            return ;
        }
        int m=(l+r)/2;
        if(p<=m) up(2*o,l,m,p,v);
        if(p>m) up(2*o+1,m+1,r,p,v);
        mi[o] = min(mi[2*o],mi[2*o+1]);
    }
    
    int qu(int o,int l,int r,int ql,int qr) {
        if(ql <= l && qr >= r) return mi[o];
        int m=(l+r)/2,ans=inf;
        if(ql<=m) ans = min(ans,qu(2*o,l,m,ql,qr));
        if(qr>m) ans = min(ans,qu(2*o+1,m+1,r,ql,qr));
        return ans;
    }
    
    int main(){
        scanf("%d",&t);
        while(t--) {
            scanf("%d",&n);
            for(int i=1;i<=n;i++) va[i].clear(),vb[i].clear();
            for(int i=1;i<=n;i++) {
                scanf("%d",&a[i]);
                va[a[i]].push_back(i);
            }
            for(int i=1;i<=n;i++) {
                scanf("%d",&b[i]);
                vb[b[i]].push_back(i);
            }
            int fg = 0;
            for(int i=1;i<=n;i++) {
                if(va[i].size() != vb[i].size()) {
                    fg = 1;break;
                }
                for(int j=0;j<vb[i].size();j++)
                    pos[vb[i][j]] = va[i][j];
            }
            if(fg) {
                puts("NO");continue;
            }
            bd(1,1,n);
            for(int i=1;i<=n;i++) {
                int minm = qu(1,1,n,1,pos[i]);
                if(minm != b[i]) {
                    fg = 1; break;
                }
                up(1,1,n,pos[i],inf);
            }
            if(fg) puts("NO");
            else puts("YES");
        }
    	return 0;
    }

[https_blog.csdn.net_ccsu_cat_article_details_100047649]: https://blog.csdn.net/ccsu_cat/article/details/100047649
[https_blog.csdn.net_Frozensmile_article_details_94366486]: https://blog.csdn.net/Frozensmile/article/details/94366486