字典树补题记录

Luogu - P6587 超超的序列 加强

AC 2023.11.19

发现 \(x \le 20\)，可以取编号 01 串的后 \(x\) 位，按字典树的形式，线段树的思想。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout<<#x<<" = "<<x<<endl;
const int N = 2e5 + 5, T = 4e6 + 5;
int n, m, a[N], point[N*20][2], num, son_num[T];
ll sum[T], tag_add[T], lastans;
inline int read(){
	int s=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){s=(s<<1)+(s<<3)+(c^48);c=getchar();}
	return s*f;
}
void insert(int val, int id){
	int p=0, x=1;
	son_num[x]++;
	sum[x] += val;
	for(int i=0;i<20;i++){
		bool k = id & (1 << i);
		if(!point[p][k])point[p][k] = ++num;
		p = point[p][k];
		if(k)x = x<<1|1;
		else x = x<<1;
		son_num[x]++;
		sum[x] += val;
	}
}
int find(int f, int y){
	int p=0, x=1;
	for(int i=0;i<f;i++){
		bool k = y & (1 << i);
		sum[x<<1] += tag_add[x] * son_num[x<<1];
		sum[x<<1|1] += tag_add[x] * son_num[x<<1|1];
		tag_add[x<<1] += tag_add[x];
		tag_add[x<<1|1] += tag_add[x];
		tag_add[x] = 0;
		if(!point[p][k])return 0; 
		p = point[p][k];
		if(k)x = x<<1|1;
		else x = x<<1;
	}
	return x;
}
void add(int f, int y, ll v){
	int p=0, x=1;
	for(int i=0;i<f;i++){
		bool k = y & (1 << i);
		sum[x<<1] += tag_add[x] * son_num[x<<1];
		sum[x<<1|1] += tag_add[x] * son_num[x<<1|1];
		tag_add[x<<1] += tag_add[x];
		tag_add[x<<1|1] += tag_add[x];
		tag_add[x] = 0;
		if(!point[p][k])return;
		p = point[p][k];
		if(k)x = x<<1|1;
		else x = x<<1;
	}
	tag_add[x] += v;
	int now_son_num = son_num[x];
	while(x){sum[x] += v * now_son_num; x>>=1;}//线段树的 pushup 
}
int main(){
	n = read(), m = read();
	for(int i=1;i<=n;i++)a[i] = read(), insert(a[i], i);
	while(m--){
		int op = read();
		int opt = (lastans + op) % 2 + 1;
		if(opt == 1){
			int x = read(), y = read(), v = read();
			add(x, y, v);
		}else{
			int x = read(), y = read();
			lastans = sum[find(x, y)];
			cout << lastans << endl;
		}
	}
	return 0;
}