CF1004F Sonya and Bitwise OR

Solution

感覺比較套路。

序列的前綴$or$有一個性質：最多變換$log$次。

所以直接建一個線段樹，每個區間對于前綴、后綴分別存下$O(log)$個斷點、$or$值以及$ans$，這樣就能夠很容易地合并以及統計答案。

時間復雜度$O(nlgn)$。

#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <cassert> #include <string.h> //#include <unordered_set> //#include <unordered_map> //#include <bits/stdc++.h>#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondusing namespace std;template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; } template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }typedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int,int> PR; typedef vector<int> VI;const lod eps=1e-11; const lod pi=acos(-1); const int oo=1<<30; const ll loo=1ll<<62; const int mods=998244353; const int MAXN=200005; const int INF=0x3f3f3f3f;//1061109567 /*--------------------------------------------------------------------*/ inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }return x*f; } int n,m,MIN,a[MAXN]; struct Node {ll ans;vector<PR> L,R;void clear() { ans=0,L.clear(),R.clear(); }Node() { clear(); } }; Node operator + (Node x,Node y) {Node z;z.L=x.L;for (int i=0,now=z.L.back().se;i<y.L.size();i++){PR t=y.L[i];if ((t.se|now)!=now) now|=t.se,z.L.PB(MP(t.fi,now));}z.R=y.R; reverse(z.R.begin(),z.R.end());for (int i=x.R.size()-1,now=z.R.back().se;i>=0;i--){PR t=x.R[i];if ((t.se|now)!=now) now|=t.se,z.R.PB(MP(t.fi,now));}reverse(z.R.begin(),z.R.end());z.ans=x.ans+y.ans;for (int i=0,now=0;i<y.L.size();i++){while (now<x.R.size()&&(x.R[now].se|y.L[i].se)>=MIN) now++;int sl=(!now?0:x.R[now-1].fi-x.L[0].fi+1);int sr=(i+1==y.L.size()?y.R.back().fi-y.L[i].fi+1:y.L[i+1].fi-y.L[i].fi);z.ans+=1ll*sl*sr;}return z; }struct Segment_Tree {Node tree[MAXN<<2];void up(int x) { tree[x]=tree[x<<1]+tree[x<<1|1]; }void build(int x,int l,int r){tree[x].clear();if (l==r){tree[x].L.PB(MP(l,a[l])),tree[x].R.PB(MP(l,a[l]));tree[x].ans=(a[l]>=MIN);return;}int mid=(l+r)>>1;build(x<<1,l,mid);build(x<<1|1,mid+1,r);up(x);}void change(int x,int l,int r,int y,int z){if (l==r){tree[x].clear();tree[x].L.PB(MP(y,z)),tree[x].R.PB(MP(y,z));tree[x].ans=(z>=MIN);return;}int mid=(l+r)>>1;if (y<=mid) change(x<<1,l,mid,y,z);else change(x<<1|1,mid+1,r,y,z);up(x);}Node query(int x,int l,int r,int L,int R){if (l>=L&&r<=R) return tree[x];int mid=(l+r)>>1;if (R<=mid) return query(x<<1,l,mid,L,R);else if (L>mid) return query(x<<1|1,mid+1,r,L,R);else return query(x<<1,l,mid,L,mid)+query(x<<1|1,mid+1,r,mid+1,R);;} } segment; int main() {n=read(),m=read(),MIN=read();for (int i=1;i<=n;i++) a[i]=read();segment.build(1,1,n);for (int i=1;i<=m;i++){int opt=read(),x=read(),y=read();if (opt==2) printf("%I64d\n",segment.query(1,1,n,x,y).ans);else segment.change(1,1,n,x,y);}return 0; }

總結

以上是生活随笔為你收集整理的CF1004F Sonya and Bitwise OR的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。