【POJ】2104 K-th Number

区间第K大数。
主席树可解。

 /* 2104 */

 #include <iostream>

 #include <sstream>

 #include <string>

 #include <map>

 #include <queue>

 #include <set>

 #include <stack>

 #include <vector>

 #include <deque>

 #include <algorithm>

 #include <cstdio>

 #include <cmath>

 #include <ctime>

 #include <cstring>

 #include <climits>

 #include <cctype>

 #include <cassert>

 #include <functional>

 #include <iterator>

 #include <iomanip>

 using namespace std;

 //#pragma comment(linker,"/STACK:102400000,1024000")

 #define sti                set<int>

 #define stpii            set<pair<int, int> >

 #define mpii            map<int,int>

 #define vi                vector<int>

 #define pii                pair<int,int>

 #define vpii            vector<pair<int,int> >

 #define rep(i, a, n)     for (int i=a;i<n;++i)

 #define per(i, a, n)     for (int i=n-1;i>=a;--i)

 #define clr                clear

 #define pb                 push_back

 #define mp                 make_pair

 #define fir                first

 #define sec                second

 #define all(x)             (x).begin(),(x).end()

 #define SZ(x)             ((int)(x).size())

 // #define lson            l, mid, rt<<1

 // #define rson            mid+1, r, rt<<1|1

 const int maxn = 1e5+;

 const int maxm = maxn * ;

 int T[maxn];

 int lson[maxm], rson[maxm], c[maxm];

 int a[maxn], b[maxn];

 int n, m;

 int tot = ;

 int Build(int l, int r) {

     int rt = tot++;

     c[rt] = ;

     if (l == r)

         return rt;

     int mid = (l + r) >> ;

     lson[rt] = Build(l, mid);

     rson[rt] = Build(mid+, r);

     return rt;

 }

 int Insert(int rt, int x, int delta) {

     int nrt = tot++, ret = nrt;

     int l = , r = m - , mid;

     c[nrt] = c[rt] + delta;

     while (l < r) {

         mid = (l + r) >> ;

         if (x <= mid) {

             lson[nrt] = tot++;

             rson[nrt] = rson[rt];

             nrt = lson[nrt];

             rt = lson[rt];

             r = mid;

         } else {

             lson[nrt] = lson[rt];

             rson[nrt] = tot++;

             nrt = rson[nrt];

             rt = rson[rt];

             l = mid + ;

         }

         c[nrt] = c[rt] + delta;

     }

     return ret;

 }

 int Query(int lrt, int rrt, int k) {

     int l = , r = m - , mid;

     int tmp;

     while (l < r) {

         mid = (l + r) >> ;

         tmp = c[lson[rrt]] - c[lson[lrt]];

         if (tmp >= k) {

             lrt = lson[lrt];

             rrt = lson[rrt];

             r = mid;

         } else {

             k -= tmp;

             lrt = rson[lrt];

             rrt = rson[rrt];

             l = mid + ;

         }

     }

     return l;

 }

 int main() {

     ios::sync_with_stdio(false);

     #ifndef ONLINE_JUDGE

         freopen("data.in", "r", stdin);

         freopen("data.out", "w", stdout);

     #endif

     int n, q;

     scanf("%d %d", &n, &q);

     rep(i, , n) {

         scanf("%d", &a[i]);

         b[i] = a[i];

     }

     sort(b, b+n);

     m = unique(b, b+n) - b;

     T[] = Build(, m-);

     rep(i, , n) {

         int id = lower_bound(b, b+m, a[i]) - b;

         T[i+] = Insert(T[i], id, );

     }

     int l, r, kth;

     int ans;

     while (q--) {

         scanf("%d %d %d", &l, &r, &kth);

         ans = b[Query(T[l-], T[r], kth)];

         printf("%d\n", ans);

     }

     #ifndef ONLINE_JUDGE

         printf("time = %d.\n", (int)clock());

     #endif

     return ;

 }

划分树可解。

 /* 2104 */

 #include <iostream>

 #include <sstream>

 #include <string>

 #include <map>

 #include <queue>

 #include <set>

 #include <stack>

 #include <vector>

 #include <deque>

 #include <algorithm>

 #include <cstdio>

 #include <cmath>

 #include <ctime>

 #include <cstring>

 #include <climits>

 #include <cctype>

 #include <cassert>

 #include <functional>

 #include <iterator>

 #include <iomanip>

 using namespace std;

 //#pragma comment(linker,"/STACK:102400000,1024000")

 #define sti                set<int>

 #define stpii            set<pair<int, int> >

 #define mpii            map<int,int>

 #define vi                vector<int>

 #define pii                pair<int,int>

 #define vpii            vector<pair<int,int> >

 #define rep(i, a, n)     for (int i=a;i<n;++i)

 #define per(i, a, n)     for (int i=n-1;i>=a;--i)

 #define clr                clear

 #define pb                 push_back

 #define mp                 make_pair

 #define fir                first

 #define sec                second

 #define all(x)             (x).begin(),(x).end()

 #define SZ(x)             ((int)(x).size())

 // #define lson            l, mid, rt<<1

 // #define rson            mid+1, r, rt<<1|1

 #define LL                __int64

 const int maxn = 1e5+;

 int order[maxn];

 int val[][maxn];

 int toLeft[][maxn];

 void Build(int l, int r, int dep) {

     if (l == r)

         return ;

     int mid = (l + r) >> ;

     int same = mid - l + ;

     rep(i, l, r+) {

         if (val[dep][i] < order[mid])

             --same;

     }

     int lpos = l, rpos = mid + ;

     rep(i, l, r+) {

         if (val[dep][i] < order[mid]) {

             val[dep+][lpos++] = val[dep][i];

         } else if (val[dep][i]==order[mid] && same>) {

             val[dep+][lpos++] = val[dep][i];

             --same;

         } else {

             val[dep+][rpos++] = val[dep][i];

         }

         toLeft[dep][i] = toLeft[dep][l-] + lpos - l;

     }

     Build(l, mid, dep+);

     Build(mid+, r, dep+);

 }

 int Query(int l, int r, int k, int L, int R, int dep) {

     if (l == r)

         return val[dep][l];

     int mid = (L + R) >> ;

     int tmp = toLeft[dep][r] - toLeft[dep][l-];

     if (tmp >= k) {

         int ll = L + toLeft[dep][l-] - toLeft[dep][L-];

         int rr = ll + tmp - ;

         return Query(ll, rr, k, L, mid, dep+);

     } else {

         k-= tmp;

         int rr = r + toLeft[dep][R] - toLeft[dep][r];

         int ll = rr - (r-l+-tmp) + ;

         return Query(ll, rr, k, mid+, R, dep+);

     }

 }

 int main() {

     ios::sync_with_stdio(false);

     #ifndef ONLINE_JUDGE

         freopen("data.in", "r", stdin);

         freopen("data.out", "w", stdout);

     #endif

     int n, q;

     int l, r, kth;

     int ans;

     scanf("%d %d", &n, &q);

     rep(i, , n+) {

         scanf("%d", &val[][i]);

         order[i] = val[][i];

     }

     sort(order+, order++n);

     Build(, n, );

     while (q--) {

         scanf("%d %d %d", &l, &r, &kth);

         ans = Query(l, r, kth, , n, );

         printf("%d\n", ans);

     }

     #ifndef ONLINE_JUDGE

         printf("time = %d.\n", (int)clock());

     #endif

     return ;

 }

数据发生器。

 from copy import deepcopy

 from random import randint, shuffle

 import shutil

 import string

 def GenDataIn():

     with open("data.in", "w") as fout:

         t = 1

         bound = 10**3

         # fout.write("%d\n" % (t))

         for tt in xrange(t):

             n = randint(100, 200)

             q = randint(100, 200)

             fout.write("%d %d\n" % (n, q))

             L = []

             for i in xrange(n):

                 x = randint(1, bound)

                 L.append(x)

             fout.write(" ".join(map(str, L)) + "\n")

             for i in xrange(q):

                 l = randint(1, n)

                 r = randint(l, n)

                 k = randint(1, r-l+1)

                 fout.write("%d %d %d\n" % (l, r, k))

 def MovDataIn():

     desFileName = "F:\eclipse_prj\workspace\hdoj\data.in"

     shutil.copyfile("data.in", desFileName)

 if __name__ == "__main__":

     GenDataIn()

     MovDataIn()