寻解难题：区间内的第K大元素(kth值)

对于20%的数据，N<=100

对于40%的数据，N<=500

对于100%的数据，N<=2000，Q<=2000000, 1 ≤ K_i ≤ N,1 ≤ X_i ≤ N

     正解是N^2预处理每个点。shu[i]表示到第i位时，有多少个数比当前枚举的点大。sum1[i]记录这个点之前包含i个比他大的点的区间数。sum2[i]就是后面的。

     f[a[i]][k+j+1]+=sum1[j]*sum2[k],这个就很好解释了，a[i]为第k+j+1大时就是他前面有j个比他大的区间数*后面有k个比他大的区间数。。。

    注意细节，因为重复出现的值不去重，所以。。前后中有一个判断是不带=的，这样才能对上。

    sum1[0]=sum2[0]=1,包含他自己。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
	int sum=0,f=1;char x=getchar();
	while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
	while(x>='0'&&x<='9'){sum=(sum<<1)+(sum<<3)+x-'0';x=getchar();}
	return sum*f;
}
int n,q,a[2005],f[2005][2005],shu[2005],num1[2005],num2[2005];
int main()
{
	freopen("kth.in","r",stdin);
	freopen("kth.out","w",stdout);
	n=read();q=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)
	{
		memset(shu,0,sizeof(shu));
		memset(num1,0,sizeof(num1));
		memset(num2,0,sizeof(num2));
		//shu[i]=1;
		for(int j=i-1;j>=1;j--)
		{
			shu[j]=shu[j+1];
			if(a[j]>a[i])shu[j]++;
			num1[shu[j]]++;
		}
		for(int j=i+1;j<=n;j++)
		{
			shu[j]=shu[j-1];
			if(a[j]>=a[i])shu[j]++;
			num2[shu[j]]++;
		}num2[0]++;num1[0]++;
		for(int j=0;j<=shu[1];j++)
		   for(int k=0;k<=shu[n];k++)
		      f[a[i]][k+j+1]+=num2[k]*num1[j];
	//	for(int j=0;j<=n;j++)cout<<num1[j]<<" ";
	//	cout<<endl;
	//	for(int j=0;j<=n;j++)cout<<num2[j]<<" ";
	//	cout<<endl;
	}
	int x,y;
	for(int i=1;i<=q;i++)
	{
		x=read();
		y=read();
		printf("%d\n",f[y][x]);
	}
}