区间第K大，主席树裸题

虽然说暴力也能过，但是如果n=1e5呢。

主席树code:

#include <bits/stdc++.h>
#define ll long long
#define lson left,mid
#define rson mid+1,right
#define imid int mid=(left+right)/2;
using namespace std;
const int maxn = 1005;
struct node
{
	int l;
	int r;
	int sum;
	node() { sum = 0; }
}tree[maxn * 20];
ll a[maxn], t[maxn];
int n, m, cnt, root[maxn];
void init()
{
	root[0] = 0;
	tree[0].l = tree[0].r = tree[0].sum = 0;
	cnt = 1;
}
void build(int num, int &rot, int left, int right)
{
	tree[cnt] = tree[rot];
	rot = cnt++;
	tree[rot].sum++;
	if (left == right)
		return;
	imid;
	if (num <= mid)
		build(num, tree[rot].l, lson);
	else
		build(num, tree[rot].r, rson);
}
ll query(int pre, int nex, int num, int left, int right)
{
	ll s = tree[tree[nex].r].sum - tree[tree[pre].r].sum;
	if (left == right)
		return left;
	imid;
	if (num > s)
		return query(tree[pre].l, tree[nex].l, num - s, lson);
	else
		return query(tree[pre].r, tree[nex].r, num, rson);
}
int main()
{
	int n, q;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &a[i]);
		t[i] = a[i];
	}
	sort(t + 1, t + 1 + n);
	cnt = unique(t + 1, t + 1 + n) - t - 1;
	for (int i = 1; i <= n; i++)
		a[i] = lower_bound(t + 1, t + 1 + cnt, a[i]) - t;
	init();
	for (int i = 1; i <= n; i++)
	{
		root[i] = root[i - 1];
		build(a[i], root[i], 1, n);
	}
	scanf("%d", &q);
	int ql, qr, k;
	while (q--)
	{
		scanf("%d%d%d", &ql, &qr, &k);
		int ans = query(root[ql - 1], root[qr], k, 1, n);
		printf("%lld\n", t[ans]);
	}
}

暴力code:

#include<stdio.h>
int main()
{
	int q,w,e,x,n,i,j,k,temp;
	scanf("%d",&n);
	int a[n]={0};
	for (i=0;i<n;i++)
	scanf("%d",a+i);
	scanf("%d",&x);
	int s[n]={0};
	for (k=0;k<x;k++)
	{
		for (i=0;i<n;i++)
		s[i]=0;
		scanf("%d %d %d",&q,&w,&e);
		for (i=q-1,j=0;i<=w-1;i++,j++)
		s[j]=a[i];
		for (i=-1;i<w-q;i++)
		{
			for (j=0;j<w-q-i;j++)
			{
				if (s[j]<s[j+1])
				{
					temp=s[j];
					s[j]=s[j+1];
					s[j+1]=temp;
				}
			}
		}
		printf("%d\n",s[e-1]);
	}
	return 0;
}