合肥做网站的的公司,模板施工视频,9377将军传奇,优化问题网站NEERC13 Problem H.Hack Protection
Solution
注意到题目中的区间与#xff0c;在左端点lll确定的情况下#xff0c;对于所有r≥lr\geq lr≥l#xff0c;ANDl,rAND_{l,r}ANDl,r只有logloglog种取值#xff0c;这是一个极为常见的性质。
于是我们从大到小枚举lll#…NEERC13 Problem H.Hack Protection
Solution
注意到题目中的区间与在左端点lll确定的情况下对于所有r≥lr\geq lr≥lANDl,rAND_{l,r}ANDl,r只有logloglog种取值这是一个极为常见的性质。
于是我们从大到小枚举lll可以维护每一位什么时候变成000即可求出每一段(li,ri,xi)(l_i,r_i,x_i)(li,ri,xi)表示ANDl,t∈[li,ri]xiAND_{l,t\in [l_i,r_i]}x_iANDl,t∈[li,ri]xi用异或前缀和SiS_iSi表示ANDl,tStxorSl−1AND_{l,t}S_t\ xor\ S_{l-1}ANDl,tSt xor Sl−1就变成求StSl−1xorxi,t∈[l,r]S_tS_l-1\ xor \ x_i,t\in[l,r]StSl−1 xor xi,t∈[l,r]的个数直接离散化之后用vectorvectorvector维护即可。
Code
#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;
}
ll ans0;
mapint,int Map;
vectorint V[MAXN];
int nxt[35],a[MAXN],s[MAXN];
setPR Set;
int solve(int l,int r,int x)
{if (lr||!Map.count(x)) return 0;int tMap[x];return lower_bound(V[t].begin(),V[t].end(),-l1)-lower_bound(V[t].begin(),V[t].end(),-r);
}
signed main()
{
// freopen(hack.in,r,stdin);
// freopen(hack.out,w,stdout);int nread(),num0;for (int i1;in;i) {a[i]read(),s[i]s[i-1]^a[i];if (!Map.count(s[i])) Map[s[i]]num;}for (int i0;i31;i) nxt[i]n1,Set.insert(MP(n1,i));for (int in;i1;i--){for (int j0;j31;j) if (!((a[i]j)1)) Set.erase(MP(nxt[j],j)),nxt[j]i,Set.insert(MP(nxt[j],j));V[Map[s[i]]].PB(-i);int lsti,nw(oo-1)1|1;for (setPR::iterator itSet.begin();it!Set.end();it) anssolve(lst,(it-fi)-1,s[i-1]^nw),nw^(1(it-se)),lst(it-fi);anssolve(lst,n,s[i-1]^nw);}printf(%lld\n,ans);return 0;
}
