传送：主席树做法http://www.cnblogs.com/candy99/p/6160704.html
做那倒带修改的主席树时就发现分块可以做，然后就试了试
思想和教主的魔法差不多，只不过那个是求>=v的有几个
既然一个数v的名次可以求，我们二分这个数就行了啊
然而……
首先，你二分到的这个数不一定在区间里出现过
比如 1 2 5 8 9
4和5的名次都是3
于是，我修改了某个区间名次的定义：
“如果一个数的名次是x，但是区间中没有次数，那么他的名次为x-1”
实现上只需要find里return l-t+(b[l]==v) 等于说明出现过
然而
该死不写了鬼知道怎么回事用主席树就行了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1e5+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x*f;
}
int n,Q,a[N],bl,m,b[N],pos[N];
int mp[N];
void reset(int x){
int l=(x-)*bl+,r=min(x*bl,n);
for(int i=l;i<=r;i++) b[i]=a[i];
sort(b+l,b+r+);
}
int flag;
int find(int x,int v){
int l=(x-)*bl+,r=min(x*bl,n),t=l;
while(l<=r){
int mid=(l+r)>>;
if(b[mid]<v) l=mid+;
else r=mid-;
}
if(b[l]==v) flag=;
return l-t+;//!
}
int rank(int l,int r,int v){
int ans=;
flag=;
if(pos[l]==pos[r]){
for(int i=l;i<=r;i++) if(a[i]<=v) ans++,flag=flag||a[i]==v;
}else{
int t=pos[l]*bl;
for(int i=l;i<=t;i++) if(a[i]<=v) ans++,flag=flag||a[i]==v;
for(int i=(pos[r]-)*bl+;i<=r;i++) if(a[i]<=v) ans++,flag=flag||a[i]==v;
for(int i=pos[l]+;i<pos[r];i++) ans+=find(i,v);
}
if(!flag) ans--;
return ans;
}
int query(int ql,int qr,int k){
int l=,r=n;
while(l<=r){
int mid=(l+r)>>;
int t=rank(ql,qr,mp[mid]);
if(t<k) l=mid+;
else r=mid-;
}
return l;
}
int main(){
freopen("in.txt","r",stdin);
freopen("1.out","w",stdout);
n=read();Q=read();
bl=sqrt(n);
m=n/bl;if(n%bl) m++;
for(int i=;i<=n;i++) a[i]=mp[i]=read(),pos[i]=(i-)/bl+;
for(int i=;i<=m;i++) reset(i);
sort(mp+,mp++n);
while(Q--){
int i=read(),j=read(),k=read();
printf("%d\n",mp[query(i,j,k)]);
}
}
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#pragma comment(linker,"/STACK:102400000,102400000")using namespace std;
#define MAX 100005
#define MAXN 1000005
#define maxnode 15
#define sigma_size 30
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lrt rt<<1
#define rrt rt<<1|1
#define middle int m=(r+l)>>1
#define LL long long
#define ull unsigned long long
#define mem(x,v) memset(x,v,sizeof(x))
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define bits(a) __builtin_popcount(a)
#define mk make_pair
#define limit 10000//const int prime = 999983;
const int INF = 0x3f3f3f3f;
const LL INFF = 0x3f3f;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-;
const LL mod = 1e9+;
const ull mx = ;/*****************************************************/
inline void RI(int &x) {
char c;
while((c=getchar())<'' || c>'');
x=c-'';
while((c=getchar())>='' && c<='') x=(x<<)+(x<<)+c-'';
}
/*****************************************************/int a[MAX];
int b[MAX];
int c[MAX];
int tmp;
bool judge(int x,int l,int r,int k){
int a1=l/tmp;
int a2=r/tmp;
int sum=;//for(int i=l;i<=r;i++) printf("%d ",a[i]);puts("");
if(a1==a2){
for(int i=l;i<=r;i++) if(a[i]<=c[x]) sum++;
if(sum>=k) return true;
return false;
}
for(int i=a1+;i<a2;i++){
sum+=upper_bound(b+i*tmp,b+(i+)*tmp,c[x])-b-i*tmp;
}
for(int i=l;i<(a1+)*tmp;i++) if(a[i]<=c[x]) sum++;
for(int i=a2*tmp;i<=r;i++) if(a[i]<=c[x]) sum++; //printf("ra %d %d %d %d\n",l,r,c[x],sum);
if(sum>=k) return true;
return false;
}int main(){
freopen("in.txt","r",stdin);
freopen("2.out","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
tmp=sqrt(n);
for(int i=;i<n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
c[i]=a[i];
}
sort(c,c+n);
for(int i=;i*tmp<n;i++){
if((i+)*tmp<=n) sort(b+i*tmp,b+(i+)*tmp);
else sort(b+i*tmp,b+n);
}
while(m--){
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
int ll=,rr=n-;
while(ll<=rr){
int mid=(ll+rr)>>;
if(judge(mid,l-,r-,k)) rr=mid-;
else ll=mid+;
}
printf("%d\n",c[ll]);
}
return ;
}
别人的AC代码
