原来水过的代码8000ms
#include<stdio.h>
#include<algorithm>
struct tnode
{int v,sit;}a[100010];
int cmp(struct tnode x,struct tnode y) {return x.v<y.v;}
int main()
{
int i,j,k,b,e,n,m,t;
freopen("c:\\input.txt","r",stdin);
freopen("c:\\output.txt","w",stdout);
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) {scanf("%d",&a[i].v);a[i].sit=i;}
std::sort(a+1,a+n+1,cmp);
for (i=1;i<=m;i++) {
scanf("%d%d%d",&b,&e,&k);
t=0;
for (j=1;j<=n;j++) {if (a[j].sit>=b&&a[j].sit<=e) t++;if (t==k) {printf("%d\n",a[j].v);break;}}
}
}
现在用点树做的 为什么会wrong answer？
#include<stdio.h>
#include<string.h>
#include<algorithm>
struct inode{int x,bh,y;}a[100001];
int ans[100001];
struct cnode{int b,e,k,re,sit;}c[5001];
#define N 131072
// 表示可用区间为[0,N)，其中N必须是2的幂数;
struct PointTree
{
int a[N+N];
int size;
void clear(){memset(this,0,sizeof(*this));}
//加点
void add(int n)
{
int i=N+n;
++size;
for (++a[i];i>1;i/=2) if (~i&1) a[i/2]++;
}
int cntLs(int n){
// 统计小于
int i=N+n,c=0; // 若统计小于等于则c=a[i];
for (;i>1;i/=2) if (i&1) c+=a[i/2];
return c;
}
int cntGt(int n){return size-a[N+n]-cntLs(n);}
//删点
void del(int n){
if (!a[n+=N]) return;
--size;
for(--a[n];n>1;n/=2) if (~n&1) --a[n/2];
}
//求点集中第i小的数(由0数起) 注意：如果i>=size 返回N-1
int operator[](int n){
int i=1;
while(i<N){
if(n<a[i]) i*=2;
else n-=a[i],i=i+i+1;
}
return i-N;
}
};
struct PointTree tr;
int cmp(struct cnode x,struct cnode y){return x.b<y.b||x.b==y.b&&x.e<y.e;}
int cmp2(struct cnode x,struct cnode y){return x.sit<y.sit;}
int cmp3(struct inode x,struct inode y){return x.x<y.x;}
int cmp4(struct inode x,struct inode y){return x.bh<y.bh;}
int main()
{
int i,j,n,m;
// freopen("c:\\input.txt","r",stdin);
// freopen("c:\\output2.txt","w",stdout);
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) {scanf("%d",&a[i].x);a[i].bh=i;}
for (i=1;i<=m;i++) {scanf("%d%d%d",&c[i].b,&c[i].e,&c[i].k);c[i].sit=i;}
std::sort(c+1,c+m+1,cmp);
std::sort(a+1,a+n+1,cmp3);
for (i=1;i<=n;i++) {a[i].y=i;ans[i]=a[i].x;}
std::sort(a+1,a+n+1,cmp4);
for (i=1;i<=m;i++) {
for (j=c[i-1].b;j<c[i].b;j++) tr.del(a[j].y);
if (c[i-1].e<c[i].e) for (j=c[i-1].e+1;j<=c[i].e;j++) tr.add(a[j].y);
else for (j=c[i].e+1;j<=c[i-1].e;j++) tr.del(a[j].y);
c[i].re=tr[c[i].k-1];
}
std::sort(c+1,c+m+1,cmp2);
for (i=1;i<=m;i++) printf("%d\n",ans[c[i].re]);
// scanf("%*d");
}