2022广西师范大学暑期训练赛 E ，K

区间 gcd+离线二分

#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 = 1e5 + 10;
int n, m , k;
map<int,int>mp;
int f[N][20];
int a[N];
int lg[N];
int  gcd(int a, int b) {
	return (!b) ? a : gcd(b, a % b);
}
void init() {
	for(int j = 1; (1 << j) <= n; j++)
		for(int i = 1; i + (1 << j) - 1 <= n; i++) {
			f[i][j] = gcd(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
		}
}
int query(int l, int r) {
	int len = lg[r - l + 1 ];
	return gcd(f[l][len], f[r - (1 << len) + 1][len]);

}
void solve() {
	cin >> n >> m;
	mp.clear();
	fer(i, 1, n)cin >> a[i], f[i][0] = a[i] ;
	init();
	fer(i, 1, n) {
		int t = i;
		int now = a[i];
		while(t <= n) {
			int l = t, r = n;
			int tt;
			while(l <= r) {
				int mid = (l + r) >> 1;
				if(query(i, mid) == now) {
					l = mid + 1;
					tt = mid;
				} else r = mid - 1;
			}
			mp[now] += (tt - t + 1);
			t = tt + 1;
			now = query(i, t);
		}
	}
	while(m--) {
		int x;
		cin >> x;
		cout << mp[x] << endl;
	}
}
signed main() {
	for(int i = 2; i <N ; i++)
	lg[i] = lg[i >> 1] + 1;
	IOS;
	int _ ;
	cin >> _;
	while( _-- )
		solve();
}

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

动态开点 注意 pushup的时候要从0开始 因为mod 7有可能为0

#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 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 = 2e5 + 10;
int n, m , k;
string s;
struct node {
	int l, r;
	int cnt;
	ll  sum[7];
} tr[N << 5];
int idx;
int rt;
void pushup(int x) {
	tr[x].cnt = tr[tr[x].l].cnt + tr[tr[x].r].cnt;
	for(int i = 0; i <= 6; i++) {
		tr[x].sum[i] = tr[tr[x].l].sum[i];
		tr[x].sum[i] += tr[tr[x].r].sum[ ((i - tr[tr[x].l].cnt) % 7 + 7) % 7 ];
	}
}
void  change(int &i, int l, int r, int x, int val) {
	if(!i)i = ++idx;
	if(l == r) {
		tr[i].cnt += val;
		tr[i].sum[1] += x * val;
		return ;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) change(tr[i].l, l, mid, x, val);
	else change(tr[i].r, mid + 1, r, x, val);
	pushup(i);
}
void solve() {
	cin >> n;
	fer(i, 1, n) {
		int op, x;
		cin >> op >> x;
		if(!op)change(rt, 1, 1e9 , x, -1);
		else if(op == 1)change(rt, 1, 1e9 , x, 1);
		else  cout << tr[rt].sum[x] << endl;
	}
}
int main() {
	IOS;
	int _ = 1;
	//cin>>_;
	while( _-- )
		solve();
}




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