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
| #include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define FL(a, b, c) for(int a = (b), a##end = (c); a <= a##end; a++)
#define FR(a, b, c) for(int a = (b), a##end = (c); a >= a##end; a--)
#define lowbit(x) ((x) & -(x))
constexpr int N = 1e6 + 10;
int w[N], n, p[N], v[N], vis[N], ans[N];
vector<int>d[N];
void add(int x, int v){while(x <= n)w[x] += v, x += lowbit(x);}
int query(int l, int r, int ans = 0){
while(r > l)ans += w[r], r -= lowbit(r);
while(l > r)ans -= w[l], l -= lowbit(l);
return ans;
}
struct A{int l, r, id;}c[N];
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
int q, k;
cin >> n >> q >> k;
FL(i, 1, n)cin >> p[i], d[p[i]].emplace_back(i);
FL(i, 1, n)cin >> v[i];
FL(i, 1, q)cin >> c[i].l >> c[i].r, c[i].id = i;
sort(c + 1, c + 1 + q, [](A&i, A&j){return i.r < j.r;});
int j = 1, z;
FL(i, 1, n){
vis[p[i]]++, add(i, v[i]);
if(vis[p[i]] >= k){
z = d[p[i]][vis[p[i]] - k];
add(z, -v[z]);
}
while(c[j].r == i)
ans[c[j].id] = query(c[j].l - 1, c[j].r), j++;
if(j > q)break;
}
FL(i, 1, q)
cout << ans[i] << endl;
return 0;
}
|
