主席树其实我还是不太懂,但是就是一个数据结构,维护权值线段树,每次维护一个新的根节点,查询的时候直接把两个版本查就行了.剩下的做题去领悟吧!
poj2104
代码:
#include<iostream> #include<cstdio> #include<cmath> #include<queue> #include<algorithm> #include<vector> #include<cstring> using namespace std; #define duke(i,a,n) for(int i = a;i <= n;i++) #define lv(i,a,n) for(int i = a;i >= n;i--) #define clean(a) memset(a,0,sizeof(a)) #define pr pair<int,int> #define mp make_pair const int INF = 1 << 30; const double eps = 1e-8; typedef long long ll; typedef double db; template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } const int MAXN = 100010; struct node { int l,r,sum; }tree[MAXN * 20]; int cnt = 0; void insert(int &num,int &x,int l,int r) { tree[cnt++] = tree[x]; x = cnt - 1; ++tree[x].sum; if(l == r) return; int mid = (l + r) >> 1; if(num <= mid) insert(num,tree[x].l,l,mid); else insert(num,tree[x].r,mid + 1,r); } int query(int lst,int now,int k,int l,int r) { if(l == r) return l; int mid = (l + r) >> 1; int t = tree[tree[now].l].sum - tree[tree[lst].l].sum; // int mid = (r + l) >> 1; if(k <= t) return query(tree[lst].l,tree[now].l,k,l,mid); else return query(tree[lst].r,tree[now].r,k - t,mid + 1,r); } struct A { int x,idx; bool operator < (const A &rhs) const { return x < rhs.x; } }; A a[MAXN]; int Rank[MAXN],root[MAXN]; int n,m; int main() { tree[0].l = tree[0].r = tree[0].sum = 0; root[0] = 0; while(scanf("%d%d",&n,&m) != EOF) { tree[0].l = tree[0].r = tree[0].sum = 0; root[0] = 0; duke(i,1,n) { read(a[i].x); a[i].idx = i; } sort(a + 1,a + n + 1); cnt = 1; duke(i,1,n) { Rank[a[i].idx] = i; } duke(i,1,n) { root[i] = root[i - 1]; insert(Rank[i],root[i],1,n); } while(m--) { int now,lst,k; read(lst);read(now);read(k); printf("%d ",a[query(root[lst - 1],root[now],k,1,n)].x); } } return 0; }