首页 > 代码库 > [POJ2761]Feed the dogs（静态区间第k小，主席树）
[POJ2761]Feed the dogs（静态区间第k小，主席树）
题目链接：http://poj.org/problem?id=2761
题意：如题
主席树只能用模版，好菜。
1 /* 2 ━━━━━┒ギリギリ♂ eye！ 3 ┓┏┓┏┓┃キリキリ♂ mind！ 4 ┛┗┛┗┛┃＼○／ 5 ┓┏┓┏┓┃ / 6 ┛┗┛┗┛┃ノ) 7 ┓┏┓┏┓┃ 8 ┛┗┛┗┛┃ 9 ┓┏┓┏┓┃ 10 ┛┗┛┗┛┃ 11 ┓┏┓┏┓┃ 12 ┛┗┛┗┛┃ 13 ┓┏┓┏┓┃ 14 ┃┃┃┃┃┃ 15 ┻┻┻┻┻┻ 16 */ 17 #include <algorithm> 18 #include <iostream> 19 #include <iomanip> 20 #include <cstring> 21 #include <climits> 22 #include <complex> 23 #include <fstream> 24 #include <cassert> 25 #include <cstdio> 26 #include <bitset> 27 #include <vector> 28 #include <deque> 29 #include <queue> 30 #include <stack> 31 #include <ctime> 32 #include <set> 33 #include <map> 34 #include <cmath> 35 using namespace std; 36 #define fr first 37 #define sc second 38 #define cl clear 39 #define BUG puts("here!!!") 40 #define W(a) while(a--) 41 #define pb(a) push_back(a) 42 #define Rint(a) scanf("%d", &a) 43 #define Rll(a) scanf("%I64d", &a) 44 #define Rs(a) scanf("%s", a) 45 #define Cin(a) cin >> a 46 #define FRead() freopen("in", "r", stdin) 47 #define FWrite() freopen("out", "w", stdout) 48 #define Rep(i, len) for(int i = 0; i < (len); i++) 49 #define For(i, a, len) for(int i = (a); i < (len); i++) 50 #define Cls(a) memset((a), 0, sizeof(a)) 51 #define Clr(a, x) memset((a), (x), sizeof(a)) 52 #define Full(a) memset((a), 0x7f7f7f, sizeof(a)) 53 #define lrt rt << 1 54 #define rrt rt << 1 | 1 55 #define pi 3.14159265359 56 #define RT return 57 #define lowbit(x) x & (-x) 58 #define onecnt(x) __builtin_popcount(x) 59 typedef long long LL; 60 typedef long double LD; 61 typedef unsigned long long ULL; 62 typedef pair<int, int> pii; 63 typedef pair<string, int> psi; 64 typedef pair<LL, LL> pll; 65 typedef map<string, int> msi; 66 typedef vector<int> vi; 67 typedef vector<LL> vl; 68 typedef vector<vl> vvl; 69 typedef vector<bool> vb; 70 71 const int maxn = 1000010; 72 int n, m; 73 int cnt, root[maxn], a[maxn], x, y, k; 74 typedef struct Node { 75 int l, r, sum; 76 }Node; 77 vector<int> h; 78 Node tree[maxn*40]; 79 80 int getid(int x) { 81 return lower_bound(h.begin(), h.end(), x) - h.begin() + 1; 82 } 83 84 void update(int l, int r, int pre, int& cur, int pos) { 85 tree[++cnt] = tree[pre], tree[cnt].sum++, cur = cnt; 86 if(l == r) return; 87 int mid = (l + r) >> 1; 88 if(mid >= pos) update(l, mid, tree[pre].l, tree[cur].l, pos); 89 else update(mid+1, r, tree[pre].r, tree[cur].r, pos); 90 } 91 92 int query(int l, int r, int x, int y, int k) { 93 if(l == r) return l; 94 int mid = (l + r) >> 1; 95 int sum = tree[tree[y].l].sum - tree[tree[x].l].sum; 96 if(sum >= k) return query(l, mid, tree[x].l, tree[y].l, k); 97 else return query(mid+1, r, tree[x].r, tree[y].r, k-sum); 98 } 99 100 int main() {101 // FRead();102 Rint(n); Rint(m);103 For(i, 1, n+1) {104 Rint(a[i]);105 h.pb(a[i]);106 }107 sort(h.begin(), h.end()), h.erase(unique(h.begin(), h.end()), h.end());108 For(i, 1, n+1) update(1, n, root[i-1], root[i], getid(a[i]));109 For(i, 1, m+1) {110 Rint(x), Rint(y), Rint(k);111 printf("%d\n", h[query(1, n, root[x-1], root[y], k)-1]);112 }113 return 0;114 }
/*━━━━━┒ギリギリ♂ eye！┓┏┓┏┓┃キリキリ♂ mind！┛┗┛┗┛┃＼○／┓┏┓┏┓┃ /┛┗┛┗┛┃ノ)┓┏┓┏┓┃┛┗┛┗┛┃┓┏┓┏┓┃┛┗┛┗┛┃┓┏┓┏┓┃┛┗┛┗┛┃┓┏┓┏┓┃┃┃┃┃┃┃┻┻┻┻┻┻*/#include <algorithm>#include <iostream>#include <iomanip>#include <cstring>#include <climits>#include <complex>#include <fstream>#include <cassert>#include <cstdio>#include <bitset>#include <vector>#include <deque>#include <queue>#include <stack>#include <ctime>#include <set>#include <map>#include <cmath>using namespace std;#define fr first#define sc second#define cl clear#define BUG puts("here!!!")#define W(a) while(a--)#define pb(a) push_back(a)#define Rint(a) scanf("%d", &a)#define Rll(a) scanf("%I64d", &a)#define Rs(a) scanf("%s", a)#define Cin(a) cin >> a#define FRead() freopen("in", "r", stdin)#define FWrite() freopen("out", "w", stdout)#define Rep(i, len) for(int i = 0; i < (len); i++)#define For(i, a, len) for(int i = (a); i < (len); i++)#define Cls(a) memset((a), 0, sizeof(a))#define Clr(a, x) memset((a), (x), sizeof(a))#define Full(a) memset((a), 0x7f7f7f, sizeof(a))#define lrt rt << 1#define rrt rt << 1 | 1#define pi 3.14159265359#define RT return#define lowbit(x) x & (-x)#define onecnt(x) __builtin_popcount(x)typedef long long LL;typedef long double LD;typedef unsigned long long ULL;typedef pair<int, int> pii;typedef pair<string, int> psi;typedef pair<LL, LL> pll;typedef map<string, int> msi;typedef vector<int> vi;typedef vector<LL> vl;typedef vector<vl> vvl;typedef vector<bool> vb;
const int maxn = 1000010;int n, m;int cnt, root[maxn], a[maxn], x, y, k;typedef struct Node {int l, r, sum;}Node;vector<int> h;Node tree[maxn*40];
int getid(int x) {return lower_bound(h.begin(), h.end(), x) - h.begin() + 1;}
void update(int l, int r, int pre, int& cur, int pos) {tree[++cnt] = tree[pre], tree[cnt].sum++, cur = cnt;if(l == r) return;int mid = (l + r) >> 1;if(mid >= pos) update(l, mid, tree[pre].l, tree[cur].l, pos);else update(mid+1, r, tree[pre].r, tree[cur].r, pos);}
int query(int l, int r, int x, int y, int k) {if(l == r) return l;int mid = (l + r) >> 1;int sum = tree[tree[y].l].sum - tree[tree[x].l].sum;if(sum >= k) return query(l, mid, tree[x].l, tree[y].l, k);else return query(mid+1, r, tree[x].r, tree[y].r, k-sum);}
int main() {// FRead();Rint(n); Rint(m);For(i, 1, n+1) {Rint(a[i]);h.pb(a[i]);}sort(h.begin(), h.end()), h.erase(unique(h.begin(), h.end()), h.end());For(i, 1, n+1) update(1, n, root[i-1], root[i], getid(a[i]));For(i, 1, m+1) {Rint(x), Rint(y), Rint(k);printf("%d\n", h[query(1, n, root[x-1], root[y], k)-1]);}return 0;}
[POJ2761]Feed the dogs（静态区间第k小，主席树）