百度之星第二场T1

题意

长度为n的序列 q次询问 l到r的前k大 是否大于等于x
主席树直接上

#include 
using namespace  std;
//#define  int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define pb  push_back
#define inf 1<<62
#define endl "\n"
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define de_bug(x) cerr << #x << "=" << x << endl
#define all(a) a.begin(),a.end()
#define IOS   std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  fer(i,a,b)  for(int i=a;i<=b;i++)
#define  der(i,a,b)  for(int i=a;i>=b;i--)
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
int n, m , k;
int rt[N];
struct node {
	int l, r, cnt;
	ll sum, val;
} tr[N << 4];
int a[N];
int b[N];
int idx;
void build(int &o, int l, int r) {
	o = ++idx;
	tr[o].cnt = tr[o].sum = tr[o].val = 0;
	if(l == r)return ;
	int  mid = l + r >> 1;
	build(tr[o].l, l, mid);
	build(tr[o].r, mid + 1, r);
}
void change(int &now, int pre, int l, int r, int tmp, int val) {
	now = ++idx;
	tr[now] = tr[pre];
	tr[now].cnt++;
	tr[now].sum += val;
	if(l == r) {
		tr[now].val = val;
		return ;
	}
	int mid = (l + r) >> 1;
	if(tmp <= mid)change(tr[now].l, tr[pre].l, l, mid, tmp, val);
	else  change(tr[now].r, tr[pre].r, mid + 1, r, tmp, val);
}
ll query(int now, int pre, int l, int r, int k) {
	if(l == r)return tr[now].val * k;
	int mid = (l + r) >> 1;
	int x = tr[tr[now].r].cnt - tr[tr[pre].r].cnt;
	if(x >= k) return query(tr[now].r, tr[pre].r, mid + 1, r, k);
	else return query(tr[now].l, tr[pre].l, l, mid, k - x) + tr[tr[now].r].sum - tr[tr[pre].r].sum;
}
int x, q;
void solve() {
	cin >> n >> q >> k >> x;
	fer(i, 1, n)cin >> a[i] , b[i] = a[i];
	sort(b + 1, b + n + 1);
	int tot = unique(b + 1, b + n + 1) - (b + 1);
	build(rt[0], 1, tot);
	fer(i, 1, n) {
		int tt = lower_bound(b + 1, b + tot + 1, a[i]) - b;
		change(rt[i], rt[i - 1], 1, tot, tt, a[i]);
	}
	while(q--) {
		int l, r;
		cin >> l >> r;
		ll ans = query(rt[r], rt[l - 1], 1, tot, k);
		if(ans >= x)cout << "Y" << endl;
		else cout << "N" << endl;
	}
}
int main() {
	IOS;
	int _ = 1;
	//cin>>_;
	while( _-- )
		solve();
}
/*
5 3 2 10
1 5 6 3 1
2 3
3 5
1 5
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91