题目概述

区间与，区间或，区间最小值。

解题报告

完了我连吉利线段树裸题都不会做。这种题一般都是考虑差分数组来分析复杂度，如果 $[L,R]$ 与(或)上 $x$ ，那么 $x$ 为 $0(1)$ 的位置会使得 $[L,R]$ 的该位变成 $0(1)$ ，对于这一位的差分数组，$[L,R]$ 除了两端都变成了 $0$ ，所以每次至多加上 $2$ 的差值并减去很多差值，有 $31$ 位就是 $62$ 的差值，总共 $62m$ 。所以可以考虑吉利线段树。

我们对于每个节点都存一个 $Same$ 表示这个节点对应的区间中，全部数相同的位的集合，当或上 $x$ 的时候，检查 $x$ 是不是 $Same$ 的子集，如果是的话，就修改这个节点并打tag（因为 $x$ 是 $Same$ 的子集所以或 $x$ 就等价于加上一个数，可以打tag），如果是与操作同理。

但是注意这是双tag线段树，所以需要强制一个tag比另一个tag优先。我们强制与tag比或tag优先，推一下会发现非常简单，只需要和权值一样与(或)上 $x$ 就行啦。

复杂度大概是 $O(62nlog_2n)$ 吧……反正肯定达不到上限……

示例程序

太久没写题都要废了，线段树都会打错。

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=500000,maxt=maxn<<2,maxa=2147483647;

int n,te,a[maxn+5],MIN[maxt+5],TA[maxt+5],TO[maxt+5],S[maxt+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return (l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r))?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline void Pushup(int p){
    int LS=p<<1,RS=p<<1|1;MIN[p]=min(MIN[LS],MIN[RS]);
    S[p]=~(MIN[LS]^MIN[RS])&maxa&S[LS]&S[RS];
}
void Build(int L,int R,int p=1){
    TA[p]=maxa;TO[p]=0;if (L==R) {MIN[p]=a[L];S[p]=maxa;return;}
    int mid=L+(R-L>>1);Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);Pushup(p);
}
inline void AddAnd(int p,int k) {MIN[p]&=k;TA[p]&=k;TO[p]&=k;}
inline void AddOr(int p,int k) {MIN[p]|=k;TA[p]|=k;TO[p]|=k;}
inline void Pushdown(int p){
    if (TA[p]<maxa) AddAnd(p<<1,TA[p]),AddAnd(p<<1|1,TA[p]),TA[p]=maxa;
    if (TO[p]) AddOr(p<<1,TO[p]),AddOr(p<<1|1,TO[p]),TO[p]=0;
}
void And(int L,int R,int k,int l=1,int r=n,int p=1){
    if (L==l&&r==R&&(~k&maxa&S[p])==(~k&maxa)) return AddAnd(p,k);int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) And(L,R,k,l,mid,p<<1); else if (L>mid) And(L,R,k,mid+1,r,p<<1|1);
    else And(L,mid,k,l,mid,p<<1),And(mid+1,R,k,mid+1,r,p<<1|1);Pushup(p);
}
void Or(int L,int R,int k,int l=1,int r=n,int p=1){
    if (L==l&&r==R&&(k&S[p])==k) return AddOr(p,k);int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) Or(L,R,k,l,mid,p<<1); else if (L>mid) Or(L,R,k,mid+1,r,p<<1|1);
    else Or(L,mid,k,l,mid,p<<1),Or(mid+1,R,k,mid+1,r,p<<1|1);Pushup(p);
}
int Ask(int L,int R,int l=1,int r=n,int p=1){
    if (L==l&&r==R) return MIN[p];int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) return Ask(L,R,l,mid,p<<1); else if (L>mid) return Ask(L,R,mid+1,r,p<<1|1);
    else return min(Ask(L,mid,l,mid,p<<1),Ask(mid+1,R,mid+1,r,p<<1|1));
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);readi(te);for (int i=1;i<=n;i++) readi(a[i]);Build(1,n);
    for (int td,L,R,x;te;te--){
        readi(td);readi(L);readi(R);
        if (td==1) readi(x),And(L,R,x);
        if (td==2) readi(x),Or(L,R,x);
        if (td==3) printf("%d\n",Ask(L,R));
    }return 0;
}