CF1004F Sonya and Bitwise OR 线段树
发布时间:2020-12-14 04:39:21 所属栏目:大数据 来源:网络整理
导读:链接 题意: ? ? 题解: 看起来很像是一棵线段树 或只会越来越大 ?一共也只有log级别 所以可以给每个点开一个vector 保存前缀和后缀 ?保证每个vector里面不超过二十个 ?所以复杂度是够的 合并答案的时候只要枚举左区间的后缀和右区间的前缀即可 ? 合并后缀的
链接 题意:? ? 题解:
#include <bits/stdc++.h> using namespace std; const int N=1e5+100; #define ll long long int n,m,x,a[N]; struct node { vector<pair<int,int> >pre,last; ll ans; node(){ans=0;} }t[N<<2]; ll getans(node &a,node &b) { ll ans=0; for(auto &i:a.last)for(auto &j:b.pre) if((i.first|j.first)>=x)ans+=(ll)i.second*(ll)j.second; return ans; } node push_up(node &a,node &b) { if(a.last.size()==0)return b; if(b.last.size()==0)return a; node temp; temp.ans=a.ans+b.ans; temp.ans+=getans(a,b); temp.last=b.last; int u=temp.last.back().first; for(auto &v: a.last) { if((v.first|u)==u)temp.last.back().second+=v.second; else temp.last.push_back({(v.first|u),v.second}),u=(u|v.first); } temp.pre=a.pre; u=temp.pre.back().first; for(auto &v: b.pre) { if((v.first|u)==u)temp.pre.back().second+=v.second; else temp.pre.push_back({(v.first|u),u=(u|v.first); } return temp; } void build(int l,int r,int pos) { if(l==r) { t[pos].last.push_back({a[l],1}); t[pos].pre.push_back({a[l],1}); t[pos].ans=a[l]>=x; return ; } int m=(l+r)>>1; build(l,pos<<1);build(m+1,r,pos<<1|1); t[pos]=push_up(t[pos<<1],t[pos<<1|1]); } void upnode(int xx,int v,int l,int pos) { if(l==r) { a[l]=v; t[pos].ans=a[l]>=x; t[pos].pre.clear();t[pos].last.clear(); t[pos].pre.push_back({v,1}); t[pos].last.push_back({v,1}); return ; } int m=(l+r)>>1; if(xx<=m)upnode(xx,v,l,pos<<1); else upnode(xx,m+1,t[pos<<1|1]); } node qsum(int L,int R,int pos) { if(L<=l&&r<=R)return t[pos]; int m=(l+r)>>1; node ans; if(L<=m) { node t=qsum(L,R,pos<<1); ans=push_up(t,ans); } if(R>m) { node t=qsum(L,pos<<1|1); ans=push_up(ans,t); } return ans; } int main() { cin>>n>>m>>x; for(int i=1;i<=n;i++)scanf("%d",&a[i]); build(1,n,1);int op,u,v; while(m--) { scanf("%d%d%d",&op,&u,&v); if(op==1)upnode(u,1,1); else printf("%lldn",qsum(u,1).ans); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |