The_flash's Blog

Recently George is preparing for the Graduate Record Examinations (GRE for short). 
Obviously the most important thing is reciting the words.
Now George is working on a word list containing N words.
He has so poor a memory that it is too hard for him to remember all of the words on the list. 
But he does find a way to help him to remember. 
He finds that if a sequence of words has a property that for all pairs of neighboring words,
the previous one is a substring of the next one, 
then the sequence of words is easy to remember.
So he decides to eliminate some words from the word list first to make the list easier for him. 
Meantime, he doesn't want to miss the important words. 
He gives each word an importance,  
which is represented by an integer ranging from -1000 to 1000,
then he wants to know which words to eliminate to 
maximize the sum of the importance of remaining words.
Negative importance just means that George thought 
it useless and is a waste of time to recite the word.
Note that although he can eliminate any number of words from the word list, 
he can never change the order between words. 
In another word, 
the order of words appeared on the word list is consistent with the order in the input. 
In addition, a word may have different meanings, so it can appear on the list more than once, 
and it may have different importance in each occurrence.
 

The first line contains an integer T(1 <= T <= 50), indicating the number of test cases.
Each test case contains several lines.
The first line contains an integer N(1 <= N <= 2 * 104), indicating the number of words.
Then N lines follows, each contains a string Si and an integer Wi, 
representing the word and its importance.
 Si contains only lowercase letters.
You can assume that the total length of all words will not exceeded 3 * 105.
 

For each test case in the input, print one line: "Case #X: Y", 
where X is the test case number (starting with 1) and 
Y is the largest importance of the remaining sequence of words.
 

1
5
a 1
ab 2
abb 3
baba 5
abbab 8

Case #1: 14

给出一串单词，每个有一个权值。顺序不变的情况下，删掉一些，使得相邻两单词，前一个是后一个的子串。
同时要求使得剩余单词权值和最大。求最大是多少。

AC自动机+fail树+线段树+DP
f[i]表示前i个单词的最大权值和
f[i]=max(f[v]+max(val[i],0))，v是i的子串
我们注意到v是i的子串这个条件还可以表示为v可以是第i个单词的每一个前缀的fail值，然后若我们之间去找v比较麻烦，
反过来想，假设f[i]求出来了，那f[i]会影响所有以它为后缀的字符串(即fail树上它的子树)，
然后我们求出fail树的dfs序(f[i]在上面影响一段区间)，
所以每次求出f值后的更新就相当于区间更新，查询就是单点查询，这个用线段树维护就好了。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <cstring>
#include <string>
#include <cmath>
#include <set>
#include <ctime>

using namespace std;

#define rep(i,l,r) for(i=l;i<=r;i++)
#define ser(i,r,l) for(i=r;i>=l;i--)
#define INF 300005
#define inf 1000000007

typedef long long ll;
priority_queue<int >QwQ;
queue<int >Q;

int num=0,cnt=0,tot,l=0,T,n,ans=0;
int to[INF<<1],h[INF<<1],s[INF],t[INF][27],in[INF],fail[INF],L[INF],R[INF];
int mx[INF*4],A[INF*4],v[INF];
char s1[INF],s2[INF];
int read()
{
    int k=0,f=1;
    char ch;
    while(ch<'0' || ch>'9'){
      if(ch=='-')f=-1;
      ch=getchar();
    }
    while(ch>='0' && ch<='9')k=(k<<1)+(k<<3)+ch-'0',ch=getchar();
    return k*f;
}
void New(int x)
{
    int i,j,k;
    rep(i,1,26)t[x][i]=0;
    fail[x]=0;
}
void hah(int x,int y)
{
    to[++l]=y,h[l]=s[x],s[x]=l;
}
void Insert(int x)
{
    int i,j,k,l1,now=1;
    scanf("%s",s1);
    l1=strlen(s1);
    v[x]=read();
    rep(i,0,l1-1){
        k=s1[i]-'a'+1;
        if(!t[now][k])t[now][k]=++tot,New(tot);
        now=t[now][k];
        s2[++num]=s1[i];
    }
    in[num]=x;
}
void build_fail()
{
    int i,j,k,p;
    fail[1]=0,Q.push(1);
    while(!Q.empty()){
        k=Q.front(),Q.pop();
        rep(i,1,26)
         if(t[k][i]){
            p=fail[k];
            while(!t[p][i])p=fail[p];
            fail[t[k][i]]=t[p][i];
            Q.push(t[k][i]);
         }
    }
}
void dfs(int x)
{
    int i,j,k;
    L[x]=++cnt;
    for(i=s[x];i;i=h[i])
     dfs(to[i]);
    R[x]=++cnt;
}
void update(int v)
{
    mx[v]=max(mx[v<<1],mx[v<<1|1]);
}
void pushdown(int v)
{
    mx[v<<1]=max(mx[v<<1],A[v]);
    mx[v<<1|1]=max(mx[v<<1|1],A[v]);
    A[v<<1]=max(A[v<<1],A[v]);
    A[v<<1|1]=max(A[v<<1|1],A[v]);
    A[v]=0;
}
void build(int v,int l,int r)
{
    int i,j,k,mid=(l+r)>>1;
    mx[v]=A[v]=0;
    if(l==r)return ;
    build(v<<1,l,mid);
    build(v<<1|1,mid+1,r);
    update(v);
}
int Query(int v,int l,int r,int x)
{
    int i,j,k,mid=(l+r)>>1;
    if(l==r)return mx[v];
    if(A[v])pushdown(v);
    if(x<=mid)return Query(v<<1,l,mid,x);
    else return Query(v<<1|1,mid+1,r,x);
    update(v);
}
void Modify(int v,int l,int r,int x,int y,int z)
{
    int i,j,k,mid=(l+r)>>1;
    if(x<=l && r<=y){
        mx[v]=max(mx[v],z);
        A[v]=max(A[v],z);
        return ;
    }
    if(A[v])pushdown(v);
    if(x<=mid)Modify(v<<1,l,mid,x,y,z);
    if(y>mid)Modify(v<<1|1,mid+1,r,x,y,z);
    update(v);
}
void solve()
{
    int i,j,k,mx=0,now=1;
    ans=0;
    build(1,1,cnt);
    rep(i,1,num){
        k=s2[i]-'a'+1;
        while(!t[now][k])now=fail[now];
        now=t[now][k];
        mx=max(mx,Query(1,1,cnt,L[now]));
        if(in[i]){
            k=v[in[i]]>0?v[in[i]]:0;
            ans=max(ans,mx+k);
            Modify(1,1,cnt,L[now],R[now],mx+k);
            mx=0,now=1;
        }
    }
    printf("%d\n",ans);
}
void init()
{
    int i,j,k=0;
    T=read();
    while(T--){
        New(1),tot=1,num=0,cnt=0,l=0;
        rep(i,1,26)t[0][i]=1;
        memset(in,0,sizeof(in));
        memset(s,0,sizeof(s));
        n=read();
        rep(i,1,n)Insert(i);
        build_fail();
        rep(i,1,tot)hah(fail[i],i);
        dfs(0);
        printf("Case #%d: ",++k);
        solve();
    }
}
void work()
{
    int i,j,k;
}
int main()
{
    init();
    work();
    return 0;
}

The best programmers of Embezzland compete to develop 
a part of the project called "e-Government"
— the system of automated statistic collecting and press analysis.

We know that any of the k citizens can become a member of the Embezzland government. 
The citizens' surnames are a1, a2, ..., ak. All surnames are different.
Initially all k citizens from this list are members of the government. 
The system should support the following options:

    Include citizen ai to the government.
    Exclude citizen ai from the government.
    Given a newspaper article text, calculate how politicized it is. To do this,
for every active government member the system counts the number of times his surname occurs 
in the text as a substring. All occurrences are taken into consideration, 
including the intersecting ones.
The degree of politicization of a text is defined as the sum of these values for 
all active government members. 

Implement this system.

The first line contains space-separated integers n and k (1 ≤ n, k ≤ 105) — 
the number of queries to the system and the number of potential government members.

Next k lines contain the surnames a1, a2, ..., ak, one per line. 
All surnames are pairwise different.

Next n lines contain queries to the system, one per line. 
Each query consists of a character that determines an operation and the operation argument,
written consecutively without a space.

Operation "include in the government" corresponds to the character "+", 
operation "exclude" corresponds to "-".
An argument of those operations is an integer between 1 and k 
— the index of the citizen involved in the operation. 
Any citizen can be included and excluded from the government 
an arbitrary number of times in any order.
Including in the government a citizen who is already there 
or excluding the citizen who isn't there changes nothing.

The operation "calculate politicization" corresponds to character "?". Its argument is a text.

All strings — surnames and texts — are non-empty sequences of lowercase Latin letters.
The total length of all surnames doesn't exceed 106, 
the total length of all texts doesn't exceed 106.

For any "calculate politicization" 
operation print on a separate line the degree of the politicization of 
the given text. Print nothing for other operations.

7 3
a
aa
ab
?aaab
-2
?aaab
-3
?aaab
+2
?aabbaa

6
4
3
6

初始给定n(<=100000)个串，总长不超过1000000，每个串初始时都是白色，
有k个操作，每次操作可以将一个串反色或给定一个串询问在这个串中所有黑色串出现次数之和。询问串总长不超过1000000。

AC自动机+fail树+dfs序+树状数组，其实还是很容易想到的

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <cstring>
#include <string>
#include <cmath>
#include <set>
#include <ctime>

using namespace std;

#define rep(i,l,r) for(i=l;i<=r;i++)
#define ser(i,r,l) for(i=r;i>=l;i--)
#define INF 1000005
#define inf 1000000007

typedef long long ll;
priority_queue<int >QwQ;

int tot,top=1,last=0,n,Q,ans=0,l=0,cnt=0;
int t[INF][30],fail[INF],id[INF],col[INF],q[INF],c[INF<<1],to[INF<<1];
int h[INF<<1],s[INF],L[INF],R[INF];
char s1[INF];
int read()
{
    int k=0,f=1;
    char ch;
    while(ch<'0' || ch>'9'){
      if(ch=='-')f=-1;
      ch=getchar();
    }
    while(ch>='0' && ch<='9')k=(k<<1)+(k<<3)+ch-'0',ch=getchar();
    return k*f;
}
int lowbit(int x){
    return x&(-x);
}
void hah(int x,int y)
{
    to[++l]=y,h[l]=s[x],s[x]=l;
}
void add(int x,int val)
{
    int i,j,k;
    for(i=x;i<=cnt;i+=lowbit(i))c[i]+=val;
}
int get_sum(int x)
{
    int i,j,k=0;
    for(i=x;i;i-=lowbit(i))k+=c[i];
    return k;
}
void Insert(int x)
{
    int i,j,k,l1,now=1;
    scanf("%s",s1);
    l1=strlen(s1);
    rep(i,0,l1-1){
        k=s1[i]-'a'+1;
        if(!t[now][k])t[now][k]=++tot;
        now=t[now][k];
    }
    col[x]=1,id[x]=now;
}
void build_fail()
{
    int i,j,k,p;
    q[0]=1,fail[1]=0;
    while(top>last){
        k=q[last++];
        rep(i,1,26)
         if(t[k][i]){
            p=fail[k];
            while(!t[p][i])p=fail[p];
            fail[t[k][i]]=t[p][i];
            q[top++]=t[k][i];
         }
    }
}
void dfs(int x)
{
    int i,j,k;
    L[x]=++cnt;
    for(i=s[x];i;i=h[i])
     dfs(to[i]);
    R[x]=++cnt;
}
void init()
{
    int i,j,k,now,p,x,l1;
    tot=1;
    rep(i,1,26)t[0][i]=1;
    Q=read(),n=read();
    rep(i,1,n)Insert(i);
    build_fail();
    rep(i,1,tot)hah(fail[i],i);
    dfs(0);
    rep(i,1,n)add(L[id[i]],1),add(R[id[i]]+1,-1);
    while(Q--){
        scanf("%s",s1);
        l1=strlen(s1);
        if(s1[0]=='?'){
            now=1,ans=0;
            rep(i,1,l1-1){
                k=s1[i]-'a'+1;
                while(!t[now][k])now=fail[now];
                now=t[now][k];
                ans+=get_sum(L[now]);
            }
            printf("%d\n",ans);
        }
        else if(s1[0]=='-'){
            sscanf(s1+1,"%d",&x);
            if(col[x]){
                col[x]=0;
                add(L[id[x]],-1),add(R[id[x]]+1,1);
            }
        }
        else{
            sscanf(s1+1,"%d",&x);
            if(!col[x]){
                col[x]=1;
                add(L[id[x]],1),add(R[id[x]]+1,-1);
            }
        }
    }
}
void work()
{
    int i,j,k;
}
int main()
{
    init();
    work();
    return 0;
}

 阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。
 打字机上只有28个按键，分别印有26个小写英文字母和'B'、'P'两个字母。

经阿狸研究发现，这个打字机是这样工作的：

l 输入小写字母，打字机的一个凹槽中会加入这个字母
(这个字母加在凹槽的最后)。

l 按一下印有'B'的按键，打字机凹槽中最后一个字母会消失。

l 按一下印有'P'的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。

例如，阿狸输入aPaPBbP，纸上被打印的字符如下：

a

aa

ab

我们把纸上打印出来的字符串从1开始顺序编号，一直到n。
打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，
在小键盘上输入两个数(x,y)（其中1≤x,y≤n），
打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。

阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，
你能帮助他么？

 输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。

第二行包含一个整数m，表示询问个数。

接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y，表示第i个询问为(x, y)。

 输出m行，其中第i行包含一个整数，表示第i个询问的答案。

aPaPBbP
3
1 2
1 3
2 3

2
1
0

 1<=N<=10^5
 
1<=M<=10^5

输入总长<=10^5

经典的AC自动机+fail树+dfs序，考试中会有点难想到用dfs序，写起来还是爽的飞起的

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <ctime>
#include <set>

using namespace std;

#define rep(i,l,r) for(i=l;i<=r;i++)
#define ser(i,r,l) for(i=r;i>=l;i--)
#define INF 100005
#define inf 100000007
typedef long long ll;
priority_queue<int >QwQ;

int l1,l=0,m,top=1,last=0,tot=1,cnt=0;
int c[INF<<1],to[INF<<1],h[INF<<1],s[INF<<1],p[INF],fa[INF],t[INF][30],q[INF],fail[INF];
int ans[INF],L[INF],R[INF];
char s1[INF];
int read()
{
    int k=0,f=1;
    char ch;
    while(ch<'0' || ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')k=(k<<1)+(k<<3)+ch-'0',ch=getchar();
    return k*f;
}
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int v)
{
    int i,j,k;
    for(i=x;i<=cnt;i+=lowbit(i))c[i]+=v;
}
int getsum(int x)
{
    int i,j,k=0;
    for(i=x;i;i-=lowbit(i))k+=c[i];
    return k;
}
void hah(int x,int y)
{
    to[++l]=y,h[l]=s[x],s[x]=l;
}
void Insert()
{
    int i,j,k,now=1,id=0;
    rep(i,0,l1-1){
        if(s1[i]=='P')p[++id]=now;
        else if(s1[i]=='B')now=fa[now];
        else {
            k=s1[i]-'a'+1;
            if(!t[now][k])t[now][k]=++tot,fa[tot]=now;
            now=t[now][k];
        }
    }
}
void build_fail()
{
    int i,j,k,p;
    q[0]=1,fail[1]=0;
    while(last<top){
        k=q[last++];
        rep(i,1,26)
         if(t[k][i]){
            p=fail[k];
            while(!t[p][i])p=fail[p];
            fail[t[k][i]]=t[p][i];
            q[top++]=t[k][i];
         }
    }
}
void dfs(int x)
{
    int i,j,k;
    L[x]=++cnt;
    for(i=s[x];i;i=h[i])
     dfs(to[i]);
    R[x]=++cnt;
}
void solve()
{
    int i,j,k,now=1,id=0;
    add(L[1],1);
    rep(i,0,l1-1){
        if(s1[i]=='P'){
            id++;
            for(j=s[id];j;j=h[j]){
                k=p[to[j]];
                ans[j]=getsum(R[k])-getsum(L[k]-1);
            }
        }
        else if(s1[i]=='B')add(L[now],-1),now=fa[now];
        else now=t[now][s1[i]-'a'+1],add(L[now],1);
    }
}
void init()
{
    int i,j,k,x,y;
    tot=1;
    rep(i,1,26)t[0][i]=1;
    scanf("%s",s1);
    l1=strlen(s1);
    Insert();
    build_fail();
    rep(i,1,tot)hah(fail[i],i);
    dfs(0);
    l=0;
    memset(s,0,sizeof(s));
    m=read();
    rep(i,1,m){
        x=read(),y=read();
        hah(y,x);
    }
    solve();
    rep(i,1,m)printf("%d\n",ans[i]);
}
void work()
{
    int i,j,k;
}
int main()
{
    init();
    work();
    return 0;
}

There are n houses in the village and some bidirectional roads connecting them. 
Every day peole always like to ask like this 
"How far is it if I want to go from house A to house B"?
Usually it hard to answer. But luckily int this village the answer is always unique,
since the roads are built in the way that there is a unique simple path
("simple" means you can't visit a place twice) between every two houses. 
Yout task is to answer all these curious people.

First line is a single integer T(T<=10), indicating the number of test cases.
For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),
the number of houses and the number of queries. 
The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, 
meaning that there is a road connecting house i and house j,with length k(0<k<=40000).
The houses are labeled from 1 to n.
Next m lines each has distinct integers i and j, 
you areato answer the distance between house i and house j.

For each test case,output m lines. Each line represents the answer of the query. 
Output a bland line after each test case.

2
3 2
1 2 10
3 1 15
1 2
2 3

2 2
1 2 100
1 2
2 1

10
25
100
100

好久木有写树上倍增了，这段时间一直在复(da)习(bai),因此今晚作死一下，写了一个裸的lca(倍增)，差点就忘记怎么写了，
特别是写完后一直以为自己写错了，找了好久错误，然后就交了个“错误代码”，结果QwQ。。。就A了。。。。
其实LCA(倍增)和RMQ差不多，只是LCA是以dfs序为基础的RMQ。。。。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

#define rep(i,l,r) for(i=l;i<=r;i++)
#define ser(i,r,l) for(i=r;i>=l;i--)
#define INF 80010
#define inf 100000007
typedef long long ll;
int n,Q,l=0,tot=0,T;
int to[INF],h[INF],s[INF],sum[INF],t[INF],deep[INF],dist[INF],p[INF],d[INF][30];
int read()
{
    int k=0,f=1;
    char ch;
    while(ch<'0' || ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')k=(k<<1)+(k<<3)+ch-'0',ch=getchar();
    return k*f;
}
void hah(int x,int y,int z)
{
    to[++l]=y,h[l]=s[x],s[x]=l,sum[l]=z;
    to[++l]=x,h[l]=s[y],s[y]=l,sum[l]=z;
}
void dfs(int x,int fa)
{
    int i,j,k;
    t[++tot]=x;
    p[x]=tot;
    for(i=s[x];i;i=h[i])
     if(to[i]==fa)continue;
     else {
         deep[to[i]]=deep[x]+1;
         dist[to[i]]=dist[x]+sum[i];
         dfs(to[i],x);
         t[++tot]=x;
     }
}
void RMQ()
{
    int i,j,k;
    rep(i,0,tot)d[i][0]=t[i];
    for(j=1;(1<<j)<tot;j++)
     for(i=0;i+(1<<j)-1<tot;i++)
      if(deep[d[i][j-1]]<deep[d[i+(1<<(j-1))][j-1]])
          d[i][j]=d[i][j-1];
      else d[i][j]=d[i+(1<<(j-1))][j-1];
}
int lca(int x,int y)
{
    int i,j,k=0;
    x=p[x],y=p[y];
    if(x>y)swap(x,y);
    while((1<<k)<=y-x+1)k++;
    k--;
    return deep[d[x][k]]<deep[d[y-(1<<k)+1][k]]?d[x][k]:d[y-(1<<k)+1][k];
}
void init()
{
    int i,j,k,x,y,z;
    T=read();
    while(T--){
        n=read(),Q=read();
        l=0,tot=-1;
        rep(i,1,n-1){
            x=read(),y=read(),z=read();
            hah(x,y,z);
        }
        rep(i,1,n)dist[i]=deep[i]=p[i]=t[i]=0;
        dfs(1,0);
        RMQ();
        //rep(i,1,n)cout<<p[i]<<endl;          
        rep(i,1,Q){
            x=read(),y=read();
            cout<<dist[x]+dist[y]-2*dist[lca(x,y)]<<endl;
            //cout<<lca(x,y)<<endl;
        }
        memset(s,0,sizeof(s));
    }
}
void work()
{
    int i,j,k;
}
int main()
{
    init();
    work();
    return 0;
}

You are working for Macrohard company in data structures department. 
After failing your previous task about key insertion you were asked to write a new data structure 
that would be able to return quickly k-th order statistics in the array segment. 
That is, given an array a[1...n] of different integer numbers, 
your program must answer a series of questions Q(i, j, k) 
in the form: "What would be the k-th number in a[i...j] segment, if this segment was sorted?" 
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3).
The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6),
the third number is 5, and therefore the answer to the question is 5.

The first line of the input file contains n --- the size of the array, 
and m --- the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000). 
The second line contains n different integer numbers not exceeding 10 9 
by their absolute values --- the array for which the answers should be given. 
The following m lines contain question descriptions, 
each description consists of three numbers: i, j, 
and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).

For each question output the answer to it --- the k-th number in sorted a[i...j] segment.

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

5
6
3

This problem has huge input,so please use c-style input(scanf,printf),
or you may got time limit exceed.

题目大意：维护一个序列，求静态的区间第k大
静态的区间第k大，主席树。。。。貌似上一篇是动态区间第k大，用的是树套树，貌似这里应该也可以用树套树吧。。。
QwQ，写的话多一个logn，我才没无聊到那种程度呢。。。。。TAT

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <cstring>
#include <string>
#include <cmath>
#include <set>
#include <ctime>

using namespace std;

#define rep(i,l,r) for(i=l;i<=r;i++)
#define ser(i,r,l) for(i=r;i>=l;i--)
#define INF 2000005
#define inf 1000000007
typedef long long ll;
int n,m,mx=0,tot=0,cnt=0;
int a[INF],L[INF],R[INF],root[INF],sum[INF],d[INF];
int read()
{
    int k=0,f=1;
    char ch;
    while(ch<'0' || ch>'9'){
      if(ch=='-')f=-1;
      ch=getchar();
    }
    while(ch>='0' && ch<='9')k=k*10+ch-'0',ch=getchar();
    return k*f;
}
void build_tree(int l,int r,int x,int &y,int v)
{
    int i,j,k,mid=(l+r)>>1;
    y=++tot;
    sum[y]=sum[x]+1;
    if(l==r)return;
    L[y]=L[x],R[y]=R[x];
    if(v<=mid)build_tree(l,mid,L[x],L[y],v);
    else build_tree(mid+1,r,R[x],R[y],v);
}
int query(int x,int y,int z)
{
    int i,j,k,l=1,r=cnt,mid;
    x=root[x-1],y=root[y];
    while(l<r){
        mid=(l+r)>>1;
        if(sum[L[y]]-sum[L[x]]>=z)x=L[x],y=L[y],r=mid;
        else z-=sum[L[y]]-sum[L[x]],x=R[x],y=R[y],l=mid+1;
    }
    return l;
}
void init()
{
    int i,j,k;
    n=read(),m=read();
    rep(i,1,n)a[i]=read(),d[++cnt]=a[i];
    sort(d+1,d+cnt+1);
    cnt=unique(d+1,d+cnt+1)-d-1;
    rep(i,1,n)a[i]=lower_bound(d+1,d+cnt+1,a[i])-d;
    rep(i,1,n)build_tree(1,cnt,root[i-1],root[i],a[i]);
}
void work()
{
    int i,j,k,x,y,z;
    while(m--){
        x=read(),y=read(),z=read();
        printf("%d\n",d[query(x,y,z)]);
    }
}
int main()
{
    init();
    work();
    return 0;
}

The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied 
with the query like to simply find the k-th smallest number of the given N numbers. 
They have developed a more powerful system such that for N numbers a[1], a[2], ..., a[N], 
you can ask it like: what is the k-th smallest number of a[i], a[i+1], ..., a[j]? 
(For some i<=j, 0<k<=j+1-i that you have given to it). 
More powerful, you can even change the value of some a[i], and continue to query, all the same.

Your task is to write a program for this computer, which

- Reads N numbers from the input (1 <= N <= 50,000)

- Processes M instructions of the input (1 <= M <= 10,000).
These instructions include querying the k-th smallest number of a[i], a[i+1], ..., a[j] 
and change some a[i] to t.

The first line of the input is a single number X(0<X<=4),the number of the test cases of the input.
Then X blocks each represent a single test case.

The first line of each block contains two integers N and M, representing N numbers and M instruction.
It is followed by N lines. The (i+1)-th line represents the number a[i]. 
Then M lines that is in the following format

Q i j k or
C i t

It represents to query the k-th number of a[i], a[i+1], ..., a[j] and change some a[i] to t,
respectively.
It is guaranteed that at any time of the operation.
Any number a[i] is a non-negative integer that is less than 1,000,000,000.

There're NO breakline between two continuous test cases.

For each querying operation, output one integer to represent the result.
(i.e. the k-th smallest number of a[i], a[i+1],..., a[j])

There're NO breakline between two continuous test cases.

2
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

3
6
3
6

题目大意：T组询问，每组给你一个序列，然后每次会修改一个值，或者询问区间第k大值，然后你回答就是的啦。。。
裸的树套树，我又写了一次线段树套平衡树，比起二逼平衡树容易多了，貌似还可以用主席树套树状数组，
等一下我再来用这个写一遍。。。。。QwQ

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <cstring>
#include <string>
#include <cmath>
#include <set>
#include <ctime>

using namespace std;

#define rep(i,l,r) for(i=l;i<=r;i++)
#define ser(i,r,l) for(i=r;i>=l;i--)
#define INF 1000005
#define inf 1000000007
typedef long long ll;
int n,m,tot=0,op=0,num=0,T;
int v[INF],size[INF],same[INF],L[INF],R[INF],weight[INF],root[200005],a[50005];
char s[5];
int read()
{
    int k=0,f=1;
    char ch;
    while(ch<'0' || ch>'9'){
      if(ch=='-')f=-1;
      ch=getchar();
    }
    while(ch>='0' && ch<='9')k=k*10+ch-'0',ch=getchar();
    return k*f;
}
void update(int x)
{
    size[x]=size[L[x]]+size[R[x]]+same[x];
}
void updown_l(int &x)
{
    int l=L[x],r=R[l];
    L[x]=R[l],R[l]=x,update(x),update(l),x=l;
}
void updown_r(int &x)
{
    int r=R[x],l=L[r];
    R[x]=L[r],L[r]=x,update(x),update(r),x=r;
}
void Insert(int &x,int y)
{
    int i,j,k;
    if(!x){
        x=++tot;
        size[x]=same[x]=1;
        weight[x]=rand();
        v[x]=y;
        return;
    }
    size[x]++;
    if(y==v[x]){
        same[x]++;
        return;
    }
    if(y<v[x]){
        Insert(L[x],y);
        if(weight[x]>weight[L[x]])updown_l(x);
    }
    else {
        Insert(R[x],y);
        if(weight[x]>weight[R[x]])updown_r(x);
    }
}
void Delet(int &x,int y)
{
    int i,j,k;
    if(!x)return;
    if(v[x]==y){
        if(same[x]>1){
            same[x]--,size[x]--;
            return;
        }
        else if(!L[x] || !R[x]){x=L[x]+R[x];return;}
        else if(weight[L[x]]<weight[R[x]])updown_l(x);
        else updown_r(x);
        Delet(x,y);
        return;
    }
    size[x]--;
    if(v[x]<y)Delet(R[x],y);
    else Delet(L[x],y);
}
void find_rank(int x,int y)
{
    int i,j,k;
    if(!x)return;
    if(v[x]==y){
        num+=size[L[x]],op+=same[x];
        return;
    }
    if(v[x]<y){
        num+=size[L[x]]+same[x];
        find_rank(R[x],y);
    }
    else find_rank(L[x],y);
}
void build_tree(int v,int l,int r,int id,int x)
{
    int i,j,k,mid=(l+r)>>1;
    Insert(root[v],x);
    if(l==r)return;
    if(id<=mid)build_tree(v<<1,l,mid,id,x);
    else build_tree(v<<1|1,mid+1,r,id,x);
}
void find_rank_QwQ(int v,int l,int r,int x,int y,int z)
{
    int i,j,k,mid=(l+r)>>1;
    if(x<=l && r<=y){
        find_rank(root[v],z);
        return;
    }
    if(x<=mid)find_rank_QwQ(v<<1,l,mid,x,y,z);
    if(y>mid)find_rank_QwQ(v<<1|1,mid+1,r,x,y,z);
}
int find_num_QwQ(int x,int y,int z)
{
    int i,j,k,mid,l=0,r=1e+9;
    while(l<r){
        mid=(l+r)>>1,num=0,op=0;
        find_rank_QwQ(1,1,n,x,y,mid);
        if(num+op<z)l=mid+1;
        else r=mid;
    }
    return l;
}
void Modify(int v,int l,int r,int id,int x)
{
    int i,j,k,mid=(l+r)>>1;
    Delet(root[v],a[id]);
    Insert(root[v],x);
    if(l==r)return;
    if(id<=mid)Modify(v<<1,l,mid,id,x);
    else Modify(v<<1|1,mid+1,r,id,x);
}
void work()
{
    int i,j,k,x,y,z;
    while(m--){
        scanf("%s",s);
        if(s[0]=='Q'){
            x=read(),y=read(),z=read();
            printf("%d\n",find_num_QwQ(x,y,z));
        }
        else {
            x=read(),y=read();
            Modify(1,1,n,x,y),a[x]=y;
        }
    }
}
void init()
{
    int i,j,k;
    T=read();
    while(T--){
        tot=0;
        memset(root,0,sizeof(root));
        memset(L,0,sizeof(L));
        memset(R,0,sizeof(R));
        n=read(),m=read();
        rep(i,1,n)
        a[i]=read(),build_tree(1,1,n,i,a[i]);
        work();
    }
}
int main()
{
    init();
    return 0;
}