2014年一码中特
首頁 > 其他 > 詳細

【BZOJ3821/UOJ46】玄學(二進制分組,線段樹)

時間:2018-12-08 16:03:56      閱讀:42865      評論:0      收藏:0      [點我收藏+]

標簽:ble   online   --   calc   ==   ret   int   一個   http   

【BZOJ3821/UOJ46】玄學(二進制分組,線段樹)

題面

BZOJ
UOJ

題解

嗚,很好的題目啊QwQ。
離線做法大概可以線段樹分治,或者直接點記錄左右兩次操作時的結果,兩個除一下就可以直接計算。
強制在線的話,一般而言,分治在線就弄成二進制分組。把所有修改操作進行二進制分組,每次新加入一個修改操作的時候考慮和前面其他的操作合并,提前構出來線段樹,按照次序插入。如果一個節點的左右兒子都填滿了修改操作的話,那么把它的兩個兒子的值進行合并。然而我們發現并不可能每個節點維護一棵線段樹來表示所有的位置的值,實際上,因為每次修改影響的都是一段區間,所以可以用\(vector\)記錄修改區間,每次只需要把左右兒子的所有斷點合并起來分段就好了,這樣子每個修改操作每次貢獻\(1\)個斷點,所以在整個線段樹上最多貢獻\(log\)個斷點,直接暴力合并就可以了。
這樣子每次查詢就可以直接在線段樹上查詢啦。
似乎說的不清楚,看看代碼就懂了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define MAX 100100
#define lson (now<<1)
#define rson (now<<1|1)
inline int read()
{
    int x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
int type,n,Q,tot,m,lans,a[MAX];
struct Node{int l,r,a,b;}t[MAX<<2];
void calc(int &a,int &b,int x,int y){a=1ll*a*x%m;b=(1ll*b*x+y)%m;}
Node operator+(Node a,Node b){calc(a.a,a.b,b.a,b.b);return a;}
vector<Node> s[MAX<<2];
void Build(int now,int l,int r)
{
    s[now].push_back((Node){1,n,1,0});
    if(l==r)return;int mid=(l+r)>>1;
    Build(lson,l,mid);Build(rson,mid+1,r);
}
void pushup(int now)
{
    s[now].clear();
    int l1=s[lson].size(),l2=s[rson].size();
    for(int i=0,j=0,l=0;i<l1&&j<l2;)
    {
        int a=s[lson][i].a,b=s[lson][i].b;
        calc(a,b,s[rson][j].a,s[rson][j].b);
        if(s[lson][i].r<=s[rson][j].r)
        {
            s[now].push_back((Node){l+1,s[lson][i].r,a,b});
            l=s[lson][i].r;
            if(s[lson][i].r==s[rson][j].r)++i,++j;
            else ++i;
        }
        else
        {
            s[now].push_back((Node){l+1,s[rson][j].r,a,b});
            l=s[rson][j].r;++j;
        }
    }
    return;
}
bool Modify(int now,int l,int r,int p,Node a)
{
    if(l==r)
    {
        if(a.l!=1)s[now].push_back((Node){1,a.l-1,1,0});
        s[now].push_back(a);
        if(a.r!=n)s[now].push_back((Node){a.r+1,n,1,0});
        return true;
    }
    int mid=(l+r)>>1;
    if(p<=mid){Modify(lson,l,mid,p,a);return false;}
    else
    {
        bool fl=Modify(rson,mid+1,r,p,a);
        if(fl)pushup(now);
        return true;
    }
}
Node Query(int now,int l,int r,int L,int R,int k)
{
    if(L==l&&r==R)
    {
        int l=0,r=s[now].size();
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(s[now][mid].l<=k&&k<=s[now][mid].r)return s[now][mid];
            if(s[now][mid].r<k)l=mid+1;
            else r=mid-1;
        }
    }
    int mid=(l+r)>>1;
    if(R<=mid)return Query(lson,l,mid,L,R,k);
    if(L>mid)return Query(rson,mid+1,r,L,R,k);
    return Query(lson,l,mid,L,mid,k)+Query(rson,mid+1,r,mid+1,R,k);
}

int main()
{
    type=read();
    n=read();m=read();
    for(int i=1;i<=n;++i)a[i]=read();
    Q=read();
    while(Q--)
    {
        int opt=read(),l=read(),r=read();
        if(type&1)l^=lans,r^=lans;
        if(opt==1)
        {
            int a=read(),b=read();++tot;
            Modify(1,1,100000,tot,(Node){l,r,a,b});
        }
        else
        {
            int x=read();if(type&1)x^=lans;
            Node u=Query(1,1,100000,l,r,x);
            lans=(1ll*u.a*a[x]+u.b)%m;
            printf("%d\n",lans);
        }
    }
    return 0;
}

【BZOJ3821/UOJ46】玄學(二進制分組,線段樹)

標簽:ble   online   --   calc   ==   ret   int   一個   http   

原文:https://www.cnblogs.com/cjyyb/p/10087923.html

(0)
(0)
   
舉報
評論 一句話評論(0
0條  
登錄后才能評論!
? 2014 bubuko.com 版權所有 魯ICP備09046678號-4
打開技術之扣,分享程序人生!
             

魯公網安備 37021202000002號

2014年一码中特