2345安全卫士
(蛋小黄（蒟蒻）)
1
#include <bits/stdc++.h>
#define int long long
#define lc p<<1
#define rc p<<1|1
using namespace std;
struct node{
int l,r,sum;
}tr[800005];
int p[600005],s[600005];
char t[600005];
int a[600005],b[600005];
int uni[600005],cnt,pt;
inline int read() {
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
inline int gd(int x){
int l=1,r=pt;
while(l<=r){
int mid=(l+r)>>1;
if(uni[mid]>=x) r=mid-1;
else l=mid+1;
}
return l;
}
void build(int p,int l,int r){
tr[p].l=l;
tr[p].r=r;
tr[p].sum=0;
if(l==r)return;
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
}
void update(int p,int pos,int d){
if(tr[p].l==tr[p].r){
tr[p].sum+=d;
return;
}
int mid=(tr[p].l+tr[p].r)>>1;
if(pos<=mid) update(lc,pos,d);
else update(rc,pos,d);
tr[p].sum=tr[lc].sum+tr[rc].sum;
}
int query(int p,int x,int y){
if(x>tr[p].r||y<tr[p].l)return 0;
if(x<=tr[p].l&&tr[p].r<=y)return tr[p].sum;
return query(lc,x,y)+query(rc,x,y);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n=read(),q=read();
for(int i=1;i<=n;i++){
p[i]=read();
s[++cnt]=p[i];
}
for(int i=1;i<=q;i++){
char op[2];
scanf("%s",op);
t[i]=op[0];
a[i]=read();
b[i]=read();
if(t[i]=='!'){
s[++cnt]=b[i];
}else{
s[++cnt]=a[i];
s[++cnt]=b[i];
}
}
sort(s+1,s+cnt+1);
pt=unique(s+1,s+cnt+1)-s-1;
for(int i=1;i<=pt;i++) uni[i]=s[i];
build(1,1,pt);
for(int i=1;i<=n;i++){
update(1,gd(p[i]),1);
}
for(int i=1;i<=q;i++){
if(t[i]=='!'){
int k=a[i],x=b[i];
update(1,gd(p[k]),-1);
p[k]=x;
update(1,gd(p[k]),1);
}else{
int l=gd(a[i]);
int r=gd(b[i]);
int ans=query(1,l,r);
if(ans==0) putchar('0');
else{
char buf[20];
int len=0;
while(ans>0){
buf[len++]=ans%10+'0';
ans/=10;
}
while(len--) putchar(buf[len]);
}
putchar('\n');
}
}
}
CZF2919
(陈泽樊)
8
这个玩意的意思是这样的：
思路分析：
首先，题目理解是一个问题；
集合属于高一的只是知识；
这集合 A= { 1,2,3 }, B= { 3,4,5 },全集 U= { 1,2,3,4,5 }，则：
① A 补集 = { 1,2 }, B 补集 = { 4,5 }即全集中没有再集合中出现的部分
② A∪B= { 1,2,3,4,5 } 即所有元素合并
③ A∩B= { 3 }即共有元素
④ A⊕B= { 1,2,4,5 }即③的补集
其次，来考虑题目本质。
我们可以将每个集合看作一个向量，其中每个元素对应一个维度。能够生成单元素{ i }意味着 i 在所有集合中的“特征”是唯一的。
随即哈希技术： 为了高效判断每个元素的唯一性，我们可以为每个集合分配一个随机哈希值，然后对每个元素计算其所属集合的哈希异或和。如果某个元素的异或和是唯一的，那么这个元素可以被单独生成。
为每个集合分配随机哈希值，每个集合 S_i 获得一个唯一的随即哈希值 H_i
对于每个元素 i ，计算所有包含i的集合的哈希异或和。如果i在某个集合的区间[ L , R ]内，那么他对 L 到 R 位置哈希贡献值 H_i .
CZF2919
(陈泽樊)
14
这不是动态开点么？？为什么要build??
@2345安全卫士
你犯了和这个人一样的错误
动态开点线段树求助！！！
2345安全卫士
(蛋小黄（蒟蒻）)
19
我让那个Deepseek帮我优化时间复杂度，他让我这么写
