2019南昌邀请赛 H. Another Sequence （fwt+离散化+线段树）

题目链接：https://nanti.jisuanke.com/t/40260
题目大意：
给两个长度为n的数组，数字大小不超过1e5，求出它们两两相或的数组c，从小到达排序后支持两种操作：
0 x ：查询位置为x的数的当前值
l r：对[l,r]区间的数开方

思路：我们通过fwt得到c数组。c[i]:i的个数。区间开方肯定用线段树维护。问题是区间长度为n * n。我们考虑对于操作：
1 10000000000
0 5
我们真的要建长度为10000000000的线段树吗？其实我们就用到1， 5， 10000000000。3个点。我们肯定考虑离散化。在操作中出现的点保留。开一个2*n的线段树就可以了。

#include <bits/stdc++.h>
#define LL long long
using namespace std;

LL N;
struct FWT_{
    void FWT_or(LL *a,LL opt) {
    for(LL i=1; i<N; i<<=1)
        for(LL p=i<<1,j=0; j<N; j+=p)
            for(LL k=0; k<i; ++k)
                if(opt==1)
                    a[i+j+k]=a[j+k]+a[i+j+k];
                else
                    a[i+j+k]=a[i+j+k]-a[j+k];
    }
    void ans_or(LL cnt1[], LL cnt2[]){
        FWT_or(cnt1, 1); FWT_or(cnt2, 1);
        for(LL i = 0; i < N; ++i) cnt1[i] = cnt1[i]*cnt2[i];
        FWT_or(cnt1, -1);
//        LL s=0;
//        for(LL i=0; i<N; i++){
//            s+=cnt1[i];
//            printf("%-3lld ", s);
//        }
//        printf("\n");
//        for(LL i=0; i<N; i++){
//            printf("%-3lld ", i);
//        }
//        printf("\n");

    }
}fwt;

struct SegTree {
    LL T[200005<<2], sum[200005<<2];
    //clear_Tree () { memset(T,0,sizeof(T)); memset(sum,0,sizeof(sum)); }
    inline void pushup(LL o) { T[o]=max(T[o<<1],T[o<<1|1]); sum[o]=sum[o<<1]+sum[o<<1|1]; }
    inline void up_data(LL o,LL l,LL r,LL x, LL y){
        if(l==r){
            T[o]=sum[o]=y;
            return ;
        }
        LL mid=l+r>>1;
        if(x<=mid) up_data(o<<1,l,mid,x, y);
        else up_data(o<<1|1,mid+1,r,x, y);
        pushup(o);
    }
    inline void add(LL o,LL l,LL r, LL ql, LL qr){//ql qr开方
        if(T[o]==1) return ;
        if(l==r){
            T[o]=sqrt(T[o]);
            sum[o]=T[o];
            return ;
        }
        LL mid=l+r>>1;
        if(qr<=mid) add(o<<1,l,mid,ql,qr);
        else if(ql>mid) add(o<<1|1,mid+1,r,ql,qr);
        else add(o<<1,l,mid,ql,mid), add(o<<1|1,mid+1,r,mid+1,qr);
        pushup(o);
    }
    inline LL query(LL o,LL l,LL r,LL x){//查询a[x]
        if(T[o]==1) return 1;
        if(l==r) return T[o];
        LL mid=l+r>>1;
        if(x<=mid) return query(o<<1,l,mid,x);
        else return query(o<<1|1,mid+1,r,x);
    }
}T;

struct Node{
    LL x, y;
    LL p;//0查询 1修改
}q[200005];

LL a[200005], b[200005], cnt1[200005], cnt2[200005];
LL c[200005], tot=0;
int main() {
    LL  n; scanf("%lld", &n);
    LL mx=0;
    for(LL i=0; i<n; i++){
        scanf("%lld", &a[i]);
        cnt1[a[i]]++;
        mx=max(a[i], mx);
    }
    for(LL i=0; i<n; i++){
        scanf("%lld", &b[i]);
        cnt2[b[i]]++;
        mx=max(b[i], mx);
    }
    N = 1;while(N <= mx) N<<=1;
    fwt.ans_or(cnt1, cnt2);//fwt

    LL Q; scanf("%lld", &Q);
    for(LL i=1; i<=Q; i++){//保存操作
        LL x, y; scanf("%lld%lld", &x, &y);
        if(x==0){
            q[i].p=0, q[i].x=y;
            c[++tot]=y;
        }
        else{
            q[i].p=1, q[i].x=x, q[i].y=y;
            c[++tot]=x; c[++tot]=y;
        }
    }
    sort(c+1, c+tot+1);
    LL cnt=unique(c+1, c+tot+1)-c-1;
    for(LL i=1; i<=Q; i++){//离散化
        if(q[i].p==0){
            q[i].x=lower_bound(c+1, c+cnt+1, q[i].x)-c;
        }
        else{
            q[i].x=lower_bound(c+1, c+cnt+1, q[i].x)-c;
            q[i].y=lower_bound(c+1, c+cnt+1, q[i].y)-c;
        }
    }
    LL s=0, pos=0;
    for(LL i=1; i<=cnt; i++){
        while(s<c[i]){
            s+=cnt1[++pos];
        }
        T.up_data(1, 1, cnt, i, pos);//把需要的点加入线段树
    }
    for(LL i=1; i<=Q; i++){
        if(q[i].p==0){
            printf("%lld\n", T.query(1, 1, cnt, q[i].x));
        }
        else{
            T.add(1, 1, cnt, q[i].x, q[i].y);
        }
    }

    return 0;
}