CF1004F Sonya and Bitwise OR 线段树

时间：2019-10-18 21:57:42 收藏：0 阅读：58

题意：

技术分享图片

题解：

看起来很像是一棵线段树
或只会越来越大一共也只有log级别所以可以给每个点开一个vector 保存前缀和后缀保证每个vector里面不超过二十个所以复杂度是够的
合并答案的时候只要枚举左区间的后缀和右区间的前缀即可
合并后缀的时候只要先设置temp为右子树的后缀然后枚举左子树的后缀与当前后缀的最后一个比较即可如果是一样的放在一起不一样或上去所以对于前缀和后缀的vector来说越后面的数字一越多！！！

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+100;
#define ll long long
int n,m,x,a[N];
struct node
{
    vector<pair<int,int> >pre,last;
    ll ans;
    node(){ans=0;}
}t[N<<2];
ll getans(node &a,node &b)
{
    ll ans=0;
    for(auto &i:a.last)for(auto &j:b.pre)
    if((i.first|j.first)>=x)ans+=(ll)i.second*(ll)j.second;
    return ans;
}
node push_up(node &a,node &b)
{    
    if(a.last.size()==0)return b;
    if(b.last.size()==0)return a;
    node temp;
    temp.ans=a.ans+b.ans;
    temp.ans+=getans(a,b);

    temp.last=b.last;
    int u=temp.last.back().first;
    for(auto &v: a.last)
    {    
        if((v.first|u)==u)temp.last.back().second+=v.second;
        else temp.last.push_back({(v.first|u),v.second}),u=(u|v.first);
    }
    temp.pre=a.pre;
    u=temp.pre.back().first;
    for(auto &v: b.pre)
    {
        if((v.first|u)==u)temp.pre.back().second+=v.second;
        else temp.pre.push_back({(v.first|u),v.second}),u=(u|v.first);
    }
    return temp;
}
void build(int l,int r,int pos)
{
    if(l==r)
    {    
        t[pos].last.push_back({a[l],1});
        t[pos].pre.push_back({a[l],1});
        t[pos].ans=a[l]>=x;
        return ;
    }
    int m=(l+r)>>1;
    build(l,m,pos<<1);build(m+1,r,pos<<1|1);
    t[pos]=push_up(t[pos<<1],t[pos<<1|1]);
}
void upnode(int xx,int v,int l,int r,int pos)
{
    if(l==r)
    {    
        a[l]=v;
        t[pos].ans=a[l]>=x;
        t[pos].pre.clear();t[pos].last.clear();
        t[pos].pre.push_back({v,1});
        t[pos].last.push_back({v,1});
        return ;
    }
    int m=(l+r)>>1;
    if(xx<=m)upnode(xx,v,l,m,pos<<1);
    else upnode(xx,v,m+1,r,pos<<1|1);
    t[pos]=push_up(t[pos<<1],t[pos<<1|1]);
}
node qsum(int L,int R,int l,int r,int pos)
{
    if(L<=l&&r<=R)return t[pos];
    int m=(l+r)>>1;
    node ans;
    if(L<=m)
    {
        node t=qsum(L,R,l,m,pos<<1);
        ans=push_up(t,ans);
    }
    if(R>m)
    {
        node t=qsum(L,R,m+1,r,pos<<1|1);
        ans=push_up(ans,t);
    }
    return ans;
}
int main()
{    
    cin>>n>>m>>x;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    build(1,n,1);int op,u,v;
    while(m--)
    {
        scanf("%d%d%d",&op,&u,&v);
        if(op==1)upnode(u,v,1,n,1);
        else printf("%lld\n",qsum(u,v,1,n,1).ans);
    }
    return 0;
}

View Code

原文：https://www.cnblogs.com/bxd123/p/11700504.html