====== Codeforces Round #665 (Div. 2) ======
[[http://codeforces.com/contest/1401|比赛链接]]
===== E. Divide Square =====
==== 题意 ====
给定一个 $10^6\times 10^6$ 的正方形,接下来给定 $n$ 条平行于 $\text{X}$ 轴的线段和 $m$ 条平行于 $\text{Y}$ 轴的线段。
问正方形被线段划分为多少区域。数据保证所有线段不共线且至少与正方形边界交于一个点。
==== 题解 ====
有结论正方形被线段划分的区域数等于 $1+$ 同时与正方形左右边界或上下边界相交的线段数 $+$ 所有线段的交点数。
然后线段树维护所有线段的交点数即可。
const int MAXN=1e5+5,M=1e6,M2=1e6+5;
struct Line{
int y,a,b;
bool operator < (const Line &b)const{
return y>1;
build(k<<1,L,M);build(k<<1|1,M+1,R);
}
void update(int k,int pos,int v){
s[k]+=v;
if(lef[k]==rig[k])return;
int mid=lef[k]+rig[k]>>1;
if(mid>=pos)update(k<<1,pos,v);
else update(k<<1|1,pos,v);
}
int query(int k,int L,int R){
if(L<=lef[k]&&rig[k]<=R)return s[k];
int ans=0,mid=lef[k]+rig[k]>>1;
if(mid>=L)ans+=query(k<<1,L,R);
if(mid
===== F. Reverse and Swap =====
==== 题意 ====
给定一个长度为 $2^n$ 的序列 $\{a\}$,接下来 $q$ 次操作:
- 将 $a_x$ 的值修改为 $k$
- 将所有 $[(i-1)2^k+1,i2^k]$ 区间翻转
- 将所有 $[(2i-2)2^k+1,(2i-1)2^k]$ 区间与 $[(2i-1)2^k+1,(2i)2^k]$ 区间交换
- 询问 $[l,r]$ 区间的和
==== 题解 ====
将 $\{a\}$ 下标改为从零开始。不难发现操作 $2$ 相当于将 $a_x$ 变为 $a_{x\oplus (2^k-1)}$,操作 $3$ 相当于将 $a_x$ 变为 $a_{x\oplus 2^k}$。
于是对于操作 $2$ 和操作 $3$,只需要维护最终下标的异或值 $\text{val}$ 即可,对于操作 $1$,只需要修改 $a_{x\oplus \text{val}}$ 即可。
对于操作 $4$,不妨先将查询区间分割为若干段形如 $[M2^k,M2^k+2^k-1]$ 的区间。
不难发现 $[0,2^k-1]$ 区间异或 $\text{val}\And (2^k-1)$ 后仍然遍历 $[0,2^k-1]$。
于是 $[M2^k,M2^k+2^k-1]$ 异或 $\text{val}$ 后变为 $[M2^k\oplus (\text{val} \And\text{~} (2^k-1)),M2^k\oplus (\text{val} \And\text{~} (2^k-1))+2^k-1]$,考虑线段树查询即可。
总时间复杂度 $O(2^n+nq)$。
const int MAXN=1<<18;
int a[MAXN],val;
LL s[MAXN<<2];
void build(int k,int L,int R){
int M=L+R>>1;
if(L==R)return s[k]=a[M],void();
build(k<<1,L,M);build(k<<1|1,M+1,R);
s[k]=s[k<<1]+s[k<<1|1];
}
void update(int k,int L,int R,int pos,int v){
if(L==R)return s[k]=v,void();
int M=L+R>>1;
if(M>=pos)update(k<<1,L,M,pos,v);
else update(k<<1|1,M+1,R,pos,v);
s[k]=s[k<<1]+s[k<<1|1];
}
LL query(int k,int L,int R,int ql,int qr,int pos){
if(ql<=L&&R<=qr)return s[k];
int M=L+R>>1,dir=(val>>pos)&1;
if(M>=qr)return query((k<<1)^dir,L,M,ql,qr,pos-1);
else if(M