【莫队 线段树】2020-2021 Winter Petrozavodsk Camp, UPC contest E. Even Intervals
2021-10-15 13:38:00 # ACM

题链

题目解析

每次询问区间 $a_l \dots a_r$ 经过排序后的偶数位置上的和，下标从 $0$ 开始；

莫队，权值线段树维护偶数位上的和；

具体来说线段树上每个节点维护：{
  偶数位，奇数位和；
  数的个数；
}
这样 $push_up$ 也很方便了；

代码实现

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
92
93
94
95
//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <deque>
#include <stack>
#include <vector>
using namespace std;
#define Pair pair<int ,int >
#define fi first
#define se second
#define ls rt<<1
#define rs rt<<1|1
#define LL long long
#define ll long long
#define MAXN 1000000000
#define mod 1000000007
#define MS 200009

int n,m,T;
int a[MS];
struct node{
	int l,r,id;
}ask[MS];
int ac[MS];
struct tree{
	int cnt,sum[2];
	int l,r;
}p[MS<<5];
int root,tot;

bool cmp(node t1, node t2){
	if (t1.l/T == t2.l/T) return t1.r < t2.r;
	else return t1.l < t2.l;
}

void push_up(int &rt){
	int LS = p[rt].l, RS = p[rt].r;
	p[rt].cnt = p[LS].cnt + p[RS].cnt;
	if (p[LS].cnt&1) p[rt].sum[0] = p[LS].sum[0] + p[RS].sum[1], p[rt].sum[1] = p[LS].sum[1] + p[RS].sum[0];
	else 			p[rt].sum[0] = p[LS].sum[0] + p[RS].sum[0], p[rt].sum[1] = p[LS].sum[1] + p[RS].sum[1];
	p[rt].sum[0] %= mod, p[rt].sum[1] %= mod;
}

void modify(int pos,int l,int r,int &rt,int val){
	if (!rt) rt = ++tot;
	if (l == r){
		p[rt].cnt += val;
		if (!p[rt].cnt) p[rt].sum[0] = 0, p[rt].sum[1] = 0;
		else p[rt].sum[0] = l, p[rt].sum[1] = 0;
		return;
	}
	int m = l+r>>1;
	if (m >= pos) modify(pos,l,m,p[rt].l,val);
	else modify(pos,m+1,r,p[rt].r,val);
	push_up(rt);
}

void remove(int index){
	modify(a[index],0,MAXN,root,-1);
}

void add(int index){
	modify(a[index],0,MAXN,root,1);
}

void solve(){
	cin >> n >> m; 
	T = sqrt(n);
	for (int i=1;i<=n;i++) cin >> a[i];
	for (int i=1;i<=m;i++) cin >> ask[i].l >> ask[i].r, ask[i].id = i, ++ask[i].l, ++ask[i].r;
	sort(ask+1,ask+m+1,cmp);
	for (int i=1,L=1,R=0;i<=m;i++){
		while (L < ask[i].l) remove(L++);
		while (L > ask[i].l) add(--L);
		while (R < ask[i].r) add(++R);
		while (R > ask[i].r) remove(R--);
		ac[ask[i].id] = p[root].sum[0];
	}
	for (int i=1;i<=m;i++) cout << ac[i] << "\n";
}

int main(){
	ios::sync_with_stdio(false);
	int ce = 1;
	//cin >> ce;
	while (ce--){
		solve();
	}
		
	return 0;	
}
Prev
2021-10-15 13:38:00 # ACM
Next