bef-> NO.23

Veröffentlicht am

[USACO13NOV]没有找零No Change

题目描述

Farmer John is at the market to purchase supplies for his farm. He has in his pocket K coins (1 <= K <= 16), each with value in the range 1..100,000,000. FJ would like to make a sequence of N purchases (1 <= N <= 100,000), where the ith purchase costs c(i) units of money (1 <= c(i) <= 10,000). As he makes this sequence of purchases, he can periodically stop and pay, with a single coin, for all the purchases made since his last payment (of course, the single coin he uses must be large enough to pay for all of these). Unfortunately, the vendors at the market are completely out of change, so whenever FJ uses a coin that is larger than the amount of money he owes, he sadly receives no changes in return!

Please compute the maximum amount of money FJ can end up with after making his N purchases in sequence. Output -1 if it is impossible for FJ to make all of his purchases.

约翰到商场购物，他的钱包里有K(1 <= K <= 16)个硬币，面值的范围是1..100,000,000。

约翰想按顺序买 N个物品(1 <= N <= 100,000)，第i个物品需要花费c(i)块钱，(1 <= c(i) <= 10,000)。

在依次进行的购买N个物品的过程中，约翰可以随时停下来付款，每次付款只用一个硬币，支付购买的内容是从上一次支付后开始到现在的这些所有物品（前提是该硬币足以支付这些物品的费用）。不幸的是，商场的收银机坏了，如果约翰支付的硬币面值大于所需的费用，他不会得到任何找零。

请计算出在购买完N个物品后，约翰最多剩下多少钱。如果无法完成购买，输出-1

输入输出格式

输入格式：

* Line 1: Two integers, K and N.

* Lines 2..1+K: Each line contains the amount of money of one of FJ’s coins.

* Lines 2+K..1+N+K: These N lines contain the costs of FJ’s intended purchases.

输出格式：

* Line 1: The maximum amount of money FJ can end up with, or -1 if FJ cannot complete all of his purchases.

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
10
3 6 
12 
15 
10 
6 
3 
3 
2 
3 
7

输出样例#1：

1
12

说明

FJ has 3 coins of values 12, 15, and 10. He must make purchases in sequence of value 6, 3, 3, 2, 3, and 7.

FJ spends his 10-unit coin on the first two purchases, then the 15-unit coin on the remaining purchases. This leaves him with the 12-unit coin.

题解

一开始傻了写了个二进制搜索，直接枚举选的集合然后顺着买，这肯定不对因为改变顺序可能更优。

这个错误做法的时间复杂度是

然后我们想假如我们要带上顺序，可以状态压缩dp!对于每个状态，我们只需要枚举最后一个加入的，让其最优，显然是个最优子结构。

恰好时间复杂度也是

完美通过了本题。

顺便说下，

是在前缀和上二分，由于价格都为正，因此前缀和满足单调性。（假如为负似乎就不可做了）

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 100005
#define maxk 18
int c[maxn] , p[maxn] , n , k , f[1<<maxk] , ans , s[maxn] , sum;
int find(int x)
{
    int l = 0 , r = n , ans = 0;
    while(l <= r)
    {
        int mid = l + r >> 1;
        if(s[mid] <= x) ans = mid , l = mid + 1;
        else r = mid - 1;
    }
    return ans;
}
inline int calc(int Sta)
{
    int ans = sum;
    for(int i = 1 ; i <= k ; ++i)
        if(Sta & (1 << (i-1) ))
            ans -= c[i];
    return ans;
}
int main()
{
     scanf("%d%d",&k,&n);
     for(int i = 1 ; i <= k ; ++i)
         scanf("%d",&c[i]) , sum += c[i];
     for(int i = 1 ; i <= n ; ++i)
         scanf("%d",&p[i]);
     for(int i = 1 ; i <= n ; ++i)
         s[i] = s[i-1] + p[i];
     std::memset(f,-1,sizeof(f));
     f[0] = 0;
     int Sets = (1<<k)-1;
     for(int i = 1 ; i <= Sets ; ++i)
        for(int j = 1 ; j <= k ; ++j)
        {
            if(!(i & (1<<(j-1))))  continue;
            f[i] = std::max(f[i] , find(s[f[i ^ (1 << (j-1))]] + c[j]));
        }
     ans = -1;
     for(int i = 1 ; i <= Sets ; ++i)
        if(f[i] == n)
            ans = std::max(ans , calc(i));
    if(ans < 0) ans = -1;
     printf("%d",ans);
}

最后我也不知道我为什么傻逼的把ans写个极小值，结果输出错了3个点。。ans=-1即可。

感觉似乎又对状压dp运用的更好了呢

[NOI2011]道路修建

题目描述

在 W 星球上有 n 个国家。为了各自国家的经济发展，他们决定在各个国家 之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬，他们只愿 意修建恰好 n – 1 条双向道路。 每条道路的修建都要付出一定的费用，这个费用等于道路长度乘以道路两端 的国家个数之差的绝对值。例如，在下图中，虚线所示道路两端分别有 2 个、4 个国家，如果该道路长度为 1，则费用为 1×|2 – 4|=2。图中圆圈里的数字表示国 家的编号。 img

由于国家的数量十分庞大，道路的建造方案有很多种，同时每种方案的修建 费用难以用人工计算，国王们决定找人设计一个软件，对于给定的建造方案，计 算出所需要的费用。请你帮助国王们设计一个这样的软件。

输入输出格式

输入格式：

输入的第一行包含一个整数 n，表示 W 星球上的国家的数量，国家从 1 到 n 编号。 接下来 n – 1 行描述道路建设情况，其中第 i 行包含三个整数 ai、bi和 ci，表 示第 i 条双向道路修建在 ai与 bi两个国家之间，长度为 ci。

输出格式：

输出一个整数，表示修建所有道路所需要的总费用。

输入输出样例

输入样例#1：

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

输出样例#1：

1
20

说明

1≤ai, bi≤n

0≤ci≤10^6

2≤n≤10^6

img

题解

充其量D2T1的难度。

任意选取点为根，dfs一个点子树大小，两部分城市数目即为子树大小和剩余部分。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 1000005
#define ll long long
ll n , head[maxn] , sz[maxn], cnt , ans;
struct edge{
    ll next , to , dis;
}e[maxn * 2];
void dfs(ll x , ll fx)
{
    sz[x] = 1;
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fx)
            dfs(e[i].to , x) , sz[x] += sz[e[i].to];
}
inline int abs(ll x){return x > 0 ? x : -x;}
void calc(ll x , ll fx , ll dis)
{
    ans += abs(sz[x] - (n - sz[x])) * dis;
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fx)
            calc(e[i].to , x , e[i].dis);
}
inline void add(ll x, ll y, ll dis)
{
    e[++cnt].next = head[x] ;
    e[cnt].to = y;
    e[cnt].dis = dis;
    head[x] = cnt;
}
int main()
{
    scanf("%lld",&n);
    ll x , y, d;
    for(int i = 1 ; i <= n-1 ; ++i)
        scanf("%lld%lld%lld",&x,&y,&d) , add(x,y,d) , add(y,x,d);
    dfs(1,0);
    calc(1,0,0);
    printf("%lld",ans);
}

求解线性同余方程组（任意模数）

题目描述

给定 n组非负整数 a_i, b_i，求解关于 x的方程组

的最小非负整数解。

输入输出格式

输入格式：

输入第一行包含整数 n。

接下来 n行，每行两个非负整数

。

输出格式：

输出一行，为满足条件的最小非负整数 xx。

输入输出样例

输入样例#1：

1
2
3
4
3
11 6
25 9
33 17

输出样例#1：

1
809

说明

说明

，保证答案不超过

。

请注意程序运行过程中进行乘法运算时结果可能有溢出的风险。

数据保证有解

题解

其实原理很简单，就是exgcd的合并。

对于第一个方程显然初始解

像数学归纳法一样，假如我们知道前k-1个方程的合并解

和合并的模数

，如何合并第k个方程呢？

将x解出后处理成非负（这时右边的解y也同样是非负）合并答案

合并的新模数

就是这么简单，却花了我1.5个小时。。

变菜了好多啊。。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 100005
#define ll long long
ll A[maxn] , B[maxn] , n;
ll exgcd(ll a , ll b , ll& x, ll& y)
{
    if(!b)
    {
        x = 1 , y = 0;
        return a;
    }
    ll g = exgcd(b , a % b , y, x);
    y -= a/b * x;
    return g;
}
inline ll mul(ll x , ll y , ll mod)
{
    ll ans = 0 , base = x;
    while(y)
    {
        if(y & 1)   ans = (ans + base) % mod;
        (base <<= 1 ) %= mod;
        y >>= 1;
    }
    return ans;
}
ll EXCRT()
{
    ll ans = (A[1] % B[1] + B[1]) % B[1] , P1 = B[1] , x , y;//init first equation
    for(int i = 2 ; i <= n ; ++i)
    {
        ll a = P1 , b = B[i] , c = (A[i] - ans % b + b) % b  , gcd = exgcd(a,b,x,y) , poc = b / gcd;
        x = mul(x , c / gcd , poc);
        x = (x + poc) % poc; // make sure x is a positive integer
        if(c % gcd) return -1;

        ans += x * P1;
        P1 *= poc;
        ans = (ans % P1 + P1) % P1;
    }
    return ans;
}
int main()
{
    scanf("%lld",&n);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%lld%lld",&B[i],&A[i]);
    printf("%lld",EXCRT());
}

注意模数相乘有可能爆long long，在它们的lcm大于long long时，那可能只能用高精度了。。。

[TJOI2009]猜数字

题目描述

现有两组数字，每组k个，第一组中的数字分别为：a1，a2，…，ak表示，第二组中的数字分别用b1，b2，…，bk表示。其中第二组中的数字是两两互素的。求最小的非负整数n，满足对于任意的i，n - ai能被bi整除。

输入输出格式

输入格式：

输入数据的第一行是一个整数k，（1 ≤ k ≤ 10）。接下来有两行，第一行是：a1，a2，…，ak，第二行是b1，b2，…，bk

输出格式：

输出所求的整数n。

输入输出样例

输入样例#1：

1
2
3
3
1 2 3
2 3 5

输出样例#1：

1
23

说明

所有数据中，第一组数字的绝对值不超过109（可能为负数），第二组数字均为不超过6000的正整数，且第二组里所有数的乘积不超过1018

每个测试点时限1秒

注意：对于C/C++语言，对64位整型数应声明为long long，如使用scanf, printf函数（以及fscanf, fprintf等），应采用%lld标识符。

题解

这道题的意义在于要注意A_i可以是负数。一开始就全处理成正的就好。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 100005
#define ll long long
ll A[maxn] , B[maxn] , n;
ll exgcd(ll a , ll b , ll& x, ll& y)
{
    if(!b)
    {
        x = 1 , y = 0;
        return a;
    }
    ll g = exgcd(b , a % b , y, x);
    y -= a/b * x;
    return g;
}
inline ll mul(ll x , ll y , ll mod)
{
    ll ans = 0 , base = x;
    while(y)
    {
        if(y & 1)   ans = (ans + base) % mod;
        (base <<= 1 ) %= mod;
        y >>= 1;
    }
    return ans;
}
ll EXCRT()
{
    for(int i = 1 ; i <= n ; ++i)
        A[i] = (A[i] % B[i] + B[i]) % B[i];
    ll ans = A[1], P1 = B[1] , x , y;//init first equation
    for(int i = 2 ; i <= n ; ++i)
    {
        ll a = P1 , b = B[i] , c = (A[i] - ans % b + b) % b  , gcd = exgcd(a,b,x,y) , poc = b / gcd;
        x = mul(x , c / gcd , poc);
        x = (x + poc) % poc; // make sure x is a positive integer
        if(c % gcd) return -1;

        ans += x * P1;
        P1 *= poc;
        ans = (ans % P1 + P1) % P1;
    }
    return ans;
}
int main()
{
    scanf("%lld",&n);
    ll x;
    for(int i = 1 ; i <= n ; ++i)
        scanf("%lld",&A[i]);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%lld",&B[i]);
    printf("%lld",EXCRT());
}

「一本通 5.4 练习 1」涂抹果酱

题目描述

Tyvj 两周年庆典要到了，Sam 想为 Tyvj 做一个大蛋糕。蛋糕俯视图是一个 N×M 的矩形，它被划分成 N×M 个边长为 1×1 的小正方形区域（可以把蛋糕当成 NNN 行 MMM 列的矩阵）。蛋糕很快做好了，但光秃秃的蛋糕肯定不好看！所以，Sam 要在蛋糕的上表面涂抹果酱。果酱有三种，分别是红果酱、绿果酱、蓝果酱，三种果酱的编号分别为 1,2,31,2,31,2,3。为了保证蛋糕的视觉效果，Admin 下达了死命令：相邻的区域严禁使用同种果酱。但 Sam 在接到这条命令之前，已经涂好了蛋糕第 KKK 行的果酱，且无法修改。
现在 Sam 想知道：能令 Admin 满意的涂果酱方案有多少种。请输出方案数%1e6。若不存在满足条件的方案，请输出 000。

输入格式

输入共三行。
第一行：N,MN, MN,M；
第二行：KKK；
第三行：MMM 个整数，表示第 KKK 行的方案。
字母的详细含义见题目描述，其他参见样例。

输出格式

输出仅一行，为可行的方案总数。

样例

样例输入

1
2
3
2 2 
1 
2 3

样例输出

1
3

样例说明

方案一 方案二 方案三
2 3 1 2 2 3 3 1 2 3 3 2

数据范围与提示

对于 30% 的数据，1≤N×M≤20；
对于 60% 的数据，1≤N≤1000,1≤M≤3；
对于 100% 的数据，1≤N≤10000,1≤M≤5。

题解

成功被一道傻逼题坑了2小时。

一看就知道是

然后写完一交WA，然后逐渐失去意识没完没了调这破题了。

总结教训：心急吃不了热豆腐！勤于输出！

想好了在写！（我是不会说今天下午我刚写了200行基环树HPD结果发现算法错了）

好吧上代码吧（就是把行压成三进制状态就可以了。。）

然后我又改成了位运算。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define maxn 10005
#define mod 1000000
#define maxm 6
int f[maxn][1<<((maxm<<1)-1)] , cnt , g[1<<maxm<<1] , ks , k , n , m , x , mar;
inline bool check(int x , int y)
{
    for(int i = 1 ; i <= m ; ++i)
    {
        if(x % 4 == y % 4) return false;
        x /= 4 , y /= 4;
    }
    return true;
}
void dfs(int tot , int cur , int las)
{
    cur <<= 2;
    if(tot == m + 1)
    {
        cur >>= 2;
        g[++cnt] = cur;
        return;
    }
    for(int i = 1 ; i <= 3 ; ++i)
        if(las != i)
            dfs(tot + 1 , cur + i , i);
}
void dp()
{
    bool flag = false;
    if(k == 1)
    {
        f[1][ks] = 1;
        for(int i = 2 ; i <= n ; ++i)
            for(int j = 1 ; j <= cnt ; ++j)
                for(int k = 1 ; k <= cnt ; ++k)
                    if(check(g[j],g[k]))
                        (f[i][g[j]] += f[i-1][g[k]]) %= mod;
    }
    else
    {
        for(int i = 1 ; i <= cnt ; ++i)
            f[1][g[i]] = 1;
        for(int i = 2 ; i <= n ; ++i)
        {
            if(i == k)
            {
                for(int j = 1 ; j <= cnt ; ++j)
                    if(check(ks , g[j]))
                        (f[i][ks] += f[i-1][g[j]]) %= mod;
            }
            else{
                for(int j = 1 ; j <= cnt ; ++j)
                    for(int k = 1 ; k <= cnt ; ++k)
                        if(check(g[j] , g[k]))
                            (f[i][g[j]] += f[i-1][g[k]]) %= mod;
            }
        }
    }
}
void write(int x)
{
    if(!x)return;
    write(x/3);
    putchar(x%3+48);
}
signed main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 1 ; i <= m ; ++i)
        scanf("%d",&x) , ks <<= 2 , ks |= x;
    dfs(1,0,-1);
    dp();
    // printf("%d",cnt);
    int ans = 0;
    for(int i = 1 ; i <= cnt ; ++i)
        (ans += f[n][g[i]]) %= mod;
    printf("%d",ans);
}

注意保证每一位不冲突，假设最低位可以是1,2,3的话必须*4才行

P4932 浏览器

题目背景

__stdcall在用Edge玩slay的时候，鼠标会经常失灵，这让她十分痛苦，因此她决定也要让你们感受一下Edge制造的痛苦。

题目描述

stdcall给了你n个点，第i个点有权值x[i]，对于两个点u和v，如果x[u] xor x[v]的结果在二进制表示下有奇数个1，那么在u和v之间连接一个Edge，现在stdcall想让你求出一共有多少个Edge。

如果你没能成功完成任务，那么__stdcall会让你痛苦一下，你这个测试点就没分了。

输入输出格式

输入格式：

一行六个整数，n，a，b，c，d，x[0]。

n是点的个数，每个点的权值需要用如下的方式生成。

你需要使用a，b，c，d和x[0]生成一个数组x，生成方式是这样的。

x_i = (ax_{i-1}^2 + bx_{i-1} + c) \mod dxi=(axi−12+bxi−1+c)modd

x[i]就是第i个点的权值，点的标号是1到n。

输出格式：

输出一个整数，表示一共有多少个Edge。

输入输出样例

输入样例#1：

1
8 98 24 20 100 44

输出样例#1：

1
12

输入样例#2：

1
1000 952537 601907 686180 1000000 673601

输出样例#2：

1
249711

说明

我们用v表示权值中的最大值。

对于前20%的数据，n<=10。

对于前40%的数据，n<=100。

对于前60%的数据，n<=1000。

对于前80%的数据，n<=1e6。

对于前90%的数据，v<=1e6。

对于100%的数据，n<=1e7，v<=1e9。

保证a，b，c，d，x[0]都是int内的非负整数。

题解

感觉非常不好。

经过了10分钟的推理后我以为是道神题，一看题解刚看到奇偶性吓得我赶紧关掉题解。

我一下子想到我前面推理用的自反性(只是联想，并不是自反性)

两个1异或会同时消失，这不就是按照每个数里1的个数奇偶分类，然后乘法原理吗？？

考试的时候一定要沉得住气，多写几个数试试，说不定能推出规律。平时常用的性质也要多积累。

往往位运算是按位统计，当然也要灵活看待。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define lowbit(x) (x & -x)
#define maxn 10000005
long long ans ,  v[maxn] , n , a , b , c , d , tot[2];
//bool isOdd[maxn];
inline int bit(long long x)
{
	int ans;
	for(ans = 0 ; x ; x -= lowbit(x))
		++ans;
	return ans;
}
int main()
{
	scanf("%lld%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d,&v[0]);
	for(int i = 1 ; i <= n ; ++i)
		v[i] = (a * v[i-1] % d* v[i-1] % d + b * v[i-1] % d + c) % d , ++tot[bit(v[i])&1];
	ans = tot[0] * tot[1];
	printf("%lld",ans);
	
}

今天晚上同时看了zyf学姐关于Splay讲解的blog和luogu某课关于线段树的讲解（甚至包括主席树初步），感觉都听懂了。

Splay我终于查到将每次查询或者新建的节点旋转到根的原因了，是因为让查询频繁的节点尽量靠近跟。基本双旋和Splay操作的实现也都明白了，删除插入什么的就不用说的，只不过把Treap的回溯时旋转保证堆序变成了Splay操作来保证复杂度。

以前看某谷劣质题解一直没大听懂主席树原理（貌似没有讲原理的），今天听懂了233，顺便看懂了很不错的数组版主席树，先发下别人的模板，有空自己写吧（NOIp前可能不会写的吧。。）

总结下关于函数式线段树变种：

类似算法总结

1、静态整体Kth

滑稽吧…sort一遍就好了。

时间复杂度O(nlogn) 空间复杂度O(n)

2、动态整体Kth

离散化后开一棵权值线段树，每个位置的值表示这个位置对应的那个数（离散化后的）有多少个，向上维护和；

查询时先查询左子树和sum，比较k和sum的大小：若k<=sum则说明第k小数在左子树中，递归查询左子树；

否则，这个数对应的就是右子树中第k-sum小的数，k-=sum，递归查询右子树。

时间复杂度

空间复杂度O(n)

平衡树诸如Treap或Splay也都能胜任。

3、静态区间Kth

对每个点以其前缀开一棵权值线段树，那么任意一段区间均可以表示成为两棵权值线段树作差，即R位置的线段树减去L-1位置上的线段树

每个点开一棵线段树空间复杂度

，MLE，考虑到后一个位置相比于前一个位置的更改只有

个节点，所以使用主席树

时间复杂度

空间复杂度

4、动态区间Kth(就是本题辣)

还是要想办法维护前缀和。如果只是同3、的前缀和的话，就要对前缀和进行

的单次修改，显然TLE。

这里考虑用树状数组维护前缀和。修改时，可以只修改

个位置，复杂度

；

查询时，依旧是R位置减去L-1位置，这时候不再是两棵线段树作差，而是log棵线段树与log棵线段树作差；跳的时候，log个节点一起跳到左子树/右子树

时间复杂度

空间复杂度

Splay模板（非区间翻转的按权值建树）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAXN 1000000
int ch[MAXN][2],f[MAXN],size[MAXN],cnt[MAXN],key[MAXN];
int sz,root;
inline void clear(int x){
	ch[x][0]=ch[x][1]=f[x]=size[x]=cnt[x]=key[x]=0;
}
inline bool get(int x){
	return ch[f[x]][1]==x;
}
inline void update(int x){
	if (x){
		size[x]=cnt[x];
		if (ch[x][0]) size[x]+=size[ch[x][0]];
		if (ch[x][1]) size[x]+=size[ch[x][1]];
	}
}
inline void rotate(int x){
	int old=f[x],oldf=f[old],whichx=get(x);
	ch[old][whichx]=ch[x][whichx^1]; f[ch[old][whichx]]=old;
	ch[x][whichx^1]=old; f[old]=x;
	f[x]=oldf;
	if (oldf)
		ch[oldf][ch[oldf][1]==old]=x;
	update(old); update(x);
}
inline void splay(int x){
	for (int fa;fa=f[x];rotate(x))
	  if (f[fa])
	    rotate((get(x)==get(fa))?fa:x);
	root=x;
}
inline void insert(int x){
	if (root==0){sz++; ch[sz][0]=ch[sz][1]=f[sz]=0; root=sz; size[sz]=cnt[sz]=1; key[sz]=x; return;}
	int now=root,fa=0;
	while(1){
		if (x==key[now]){
			cnt[now]++; update(now); update(fa); splay(now); break;
		}
		fa=now;
		now=ch[now][key[now]<x];
		if (now==0){
			sz++;
			ch[sz][0]=ch[sz][1]=0;
			f[sz]=fa;
			size[sz]=cnt[sz]=1;
			ch[fa][key[fa]<x]=sz;
			key[sz]=x;
			update(fa);
			splay(sz);
			break;
		}
	}
}
inline int find(int x){
	int now=root,ans=0;
	while(1){
		if (x<key[now])
		  now=ch[now][0];
		else{
			ans+=(ch[now][0]?size[ch[now][0]]:0);
			if (x==key[now]){
				splay(now); return ans+1;
			}
			ans+=cnt[now];
			now=ch[now][1];
		}
	}
}
inline int findx(int x){
	int now=root;
	while(1){
		if (ch[now][0]&&x<=size[ch[now][0]])
		  now=ch[now][0];
		else{
			int temp=(ch[now][0]?size[ch[now][0]]:0)+cnt[now];
			if (x<=temp) return key[now];
			x-=temp; now=ch[now][1];
		}
	}
}
inline int pre(){
	int now=ch[root][0];
	while (ch[now][1]) now=ch[now][1];
	return now;
}
inline int next(){
	int now=ch[root][1];
	while (ch[now][0]) now=ch[now][0];
	return now;
}
inline void del(int x){
	int whatever=find(x);
	if (cnt[root]>1){cnt[root]--; update(root); return;}
	if (!ch[root][0]&&!ch[root][1]) {clear(root); root=0; return;}
	if (!ch[root][0]){
		int oldroot=root; root=ch[root][1]; f[root]=0; clear(oldroot); return;
	}
	else if (!ch[root][1]){
		int oldroot=root; root=ch[root][0]; f[root]=0; clear(oldroot); return;
	}
	int leftbig=pre(),oldroot=root;
	splay(leftbig);
	ch[root][1]=ch[oldroot][1];
	f[ch[oldroot][1]]=root;
	clear(oldroot);
	update(root); 
}
int main(){
	int n,opt,x;
	scanf("%d",&n);
	for (int i=1;i<=n;++i){
		scanf("%d%d",&opt,&x);
		switch(opt){
			case 1: insert(x); break;
			case 2: del(x); break;
			case 3: printf("%d\n",find(x)); break;
			case 4: printf("%d\n",findx(x)); break;
			case 5: insert(x); printf("%d\n",key[pre()]); del(x); break;
			case 6: insert(x); printf("%d\n",key[next()]); del(x); break;
		}
	}
}

主席树（静态区间第k大）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cctype>
#include<vector>
#include<map>
#include<queue>
#define rep(i, x, y) for (int i = (x); i <= (y); i ++)
#define down(i, x, y) for (int i = (x); i >= (y); i --)
#define mid (l+r)/2
#define lc o<<1
#define rc o<<1|1
#define pb push_back
#define mp make_pair
#define Pair pair<int, int>
#define F first
#define S second
#define B begin()
#define E end()
using namespace std;
typedef long long LL;
//head
 
const int N = 100010, LOG = 20;
int n, m, q, tot = 0;
int a[N], b[N];
int T[N], sum[N*LOG], L[N*LOG], R[N*LOG];
 
inline int build(int l, int r)
{
	int rt = ++ tot;
	if (l < r){
		L[rt] = build(l, mid);
		R[rt] = build(mid+1, r);
	}
	return rt;
}
 
inline int update(int pre, int l, int r, int x)
{
	int rt = ++ tot;
	L[rt] = L[pre]; R[rt] = R[pre]; sum[rt] = sum[pre] + 1; 
	if (l < r){
		if (x <= mid) L[rt] = update(L[pre], l, mid, x);
		else R[rt] = update(R[pre], mid+1, r, x);
	}
	return rt;
}
 
inline int query(int u, int v, int l, int r, int k)
{
	if (l == r) return l;
	int x = sum[L[v]] - sum[L[u]];
	if (x >= k) return query(L[u], L[v], l, mid, k);
	else return query(R[u], R[v], mid+1, r, k-x);
}
 
int main()
{
	int Test; scanf("%d", &Test);
	while (Test --){
		tot = 0;
		memset(T, 0, sizeof T); memset(sum, 0, sizeof sum);
		memset(L, 0, sizeof L); memset(R, 0, sizeof R);
		scanf("%d%d", &n, &q);
		rep(i, 1, n) scanf("%d", &a[i]), b[i] = a[i];
		sort(b+1, b+1+n);
		m = unique(b+1, b+1+n)-b-1;
		T[0] = build(1, m);
		rep(i, 1, n){
			a[i] = lower_bound(b+1, b+1+m, a[i]) - b;
			T[i] = update(T[i-1], 1, m, a[i]);
		}
		while (q --){
			int x, y, z; scanf("%d%d%d", &x, &y, &z);
			int p = query(T[x-1], T[y], 1, m, z);
			printf("%d\n", b[p]);
		}
	}
	return 0;
}