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;
}