地产网站建设互动营销,高端网站建设慕枫,北京专业做网站,wordpress无法设置CF1004F Sonya and Bitwise OR
Solution
感觉比较套路。
序列的前缀ororor有一个性质#xff1a;最多变换logloglog次。
所以直接建一个线段树#xff0c;每个区间对于前缀、后缀分别存下O(log)O(log)O(log)个断点、ororor值以及ansansans#xff0c;这样就能够很容易地…CF1004F Sonya and Bitwise OR
Solution
感觉比较套路。
序列的前缀ororor有一个性质最多变换logloglog次。
所以直接建一个线段树每个区间对于前缀、后缀分别存下O(log)O(log)O(log)个断点、ororor值以及ansansans这样就能够很容易地合并以及统计答案。
时间复杂度O(nlgn)O(nlgn)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;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN200005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
int n,m,MIN,a[MAXN];
struct Node
{ll ans;vectorPR L,R;void clear() { ans0,L.clear(),R.clear(); }Node() { clear(); }
};
Node operator (Node x,Node y)
{Node z;z.Lx.L;for (int i0,nowz.L.back().se;iy.L.size();i){PR ty.L[i];if ((t.se|now)!now) now|t.se,z.L.PB(MP(t.fi,now));}z.Ry.R; reverse(z.R.begin(),z.R.end());for (int ix.R.size()-1,nowz.R.back().se;i0;i--){PR tx.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.ansx.ansy.ans;for (int i0,now0;iy.L.size();i){while (nowx.R.size()(x.R[now].se|y.L[i].se)MIN) now;int sl(!now?0:x.R[now-1].fi-x.L[0].fi1);int sr(i1y.L.size()?y.R.back().fi-y.L[i].fi1:y.L[i1].fi-y.L[i].fi);z.ans1ll*sl*sr;}return z;
}struct Segment_Tree
{Node tree[MAXN2];void up(int x) { tree[x]tree[x1]tree[x1|1]; }void build(int x,int l,int r){tree[x].clear();if (lr){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(lr)1;build(x1,l,mid);build(x1|1,mid1,r);up(x);}void change(int x,int l,int r,int y,int z){if (lr){tree[x].clear();tree[x].L.PB(MP(y,z)),tree[x].R.PB(MP(y,z));tree[x].ans(zMIN);return;}int mid(lr)1;if (ymid) change(x1,l,mid,y,z);else change(x1|1,mid1,r,y,z);up(x);}Node query(int x,int l,int r,int L,int R){if (lLrR) return tree[x];int mid(lr)1;if (Rmid) return query(x1,l,mid,L,R);else if (Lmid) return query(x1|1,mid1,r,L,R);else return query(x1,l,mid,L,mid)query(x1|1,mid1,r,mid1,R);;}
} segment;
int main()
{nread(),mread(),MINread();for (int i1;in;i) a[i]read();segment.build(1,1,n);for (int i1;im;i){int optread(),xread(),yread();if (opt2) printf(%I64d\n,segment.query(1,1,n,x,y).ans);else segment.change(1,1,n,x,y);}return 0;
}
