[DS记录]Loj#6507. 「雅礼集训 2018 Day7」A

**题意** ： 维护一个长为 $n$ 的序列 $A$ ，支持下列操作 : - 区间或 - 区间与 - 区间求 $\min$ $n,m\leq 5\times 10^5$ ，时限$\texttt{2s}$。 ------------ $\text{Seg-Beats}$ 。 对于每个节点，记录区间 $\rm ans,or,min$ 。 - 对于与 $x$ 的操作： - 若区间 ${\rm or}\subseteq x$ ，则无影响，直接返回。 - 若 ${\rm and}\&x={\rm or}\&x$ ，则操作后区间内是清一色的，打标记维护。 - 对于其他情况，暴力递归。 - 对于或 $x$ 的操作： - 若区间 ${\rm and}\supseteq x$ ，则无影响，直接返回。 - 若 ${\rm and}|x={\rm or}|x$ ，则操作后区间内是清一色的，打标记维护。 - 对于其他情况，暴力递归。 考虑复杂度，我们发现一次暴力递归必定使得区间内的某一非纯色位变为纯色。于是一个节点的势能上界为 $O(w)$。 而每次修改会使得 $O(\log n)$ 个点的势能不可预期地变化。总复杂度为 $O\big((n+m\log n)w\big)$。 ```cpp #include<algorithm> #include<cstdio> #define uint unsigned int #define MaxN 500500 using namespace std; const uint INF=-1u; struct Node{ uint ands,ors,x,tg; inline void ladd(uint t) {ands=ors=x=tg=t;} }a[1<<20|500]; inline void up(int u){ a[u].x=min(a[u<<1].x,a[u<<1|1].x); a[u].ors=a[u<<1].ors|a[u<<1|1].ors; a[u].ands=a[u<<1].ands&a[u<<1|1].ands; } int x[MaxN]; void build(int l,int r,int u=1) { a[u].tg=INF; if (l==r){ a[u].x=a[u].ors=a[u].ands=x[l]; return ; }int mid=(l+r)>>1; build(l,mid,u<<1); build(mid+1,r,u<<1|1); up(u); } inline void ladd(int u){ if (a[u].tg!=INF){ a[u<<1].ladd(a[u].tg); a[u<<1|1].ladd(a[u].tg); a[u].tg=INF; } } int wfl,wfr;uint wfc,ret; void tand(int l,int r,int u) { if ((a[u].ors&wfc)==a[u].ors)return ; if (wfl<=l&&r<=wfr&&(a[u].ors&wfc)==(a[u].ands&wfc)) {a[u].ladd(a[u].ors&wfc);return ;} int mid=(l+r)>>1;ladd(u); if (wfl<=mid)tand(l,mid,u<<1); if (mid<wfr)tand(mid+1,r,u<<1|1); up(u); } void tor(int l,int r,int u) { if ((a[u].ands|wfc)==a[u].ands)return ; if (wfl<=l&&r<=wfr&&(a[u].ors|wfc)==(a[u].ands|wfc)) {a[u].ladd(a[u].ors|wfc);return ;} int mid=(l+r)>>1;ladd(u); if (wfl<=mid)tor(l,mid,u<<1); if (mid<wfr)tor(mid+1,r,u<<1|1); up(u); } void qry(int l,int r,int u) { if (wfl<=l&&r<=wfr){ret=min(ret,a[u].x);return ;} int mid=(l+r)>>1;ladd(u); if (wfl<=mid)qry(l,mid,u<<1); if (mid<wfr)qry(mid+1,r,u<<1|1); } int n,m; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++)scanf("%u",&x[i]); build(1,n,1); for (int i=1,op;i<=m;i++){ scanf("%d%d%d",&op,&wfl,&wfr); if (op==1){scanf("%u",&wfc);tand(1,n,1);} if (op==2){scanf("%u",&wfc);tor(1,n,1);} if (op==3){ret=INF;qry(1,n,1);printf("%u\n",ret);} }return 0; } ```