# 【BZOJ3821/UOJ46】玄学（二进制分组，线段树）

## 题解

``````#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)
{
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()
{
while(Q--)
{
if(type&1)l^=lans,r^=lans;
if(opt==1)
{
Modify(1,1,100000,tot,(Node){l,r,a,b});
}
else
{
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】玄学（二进制分组，线段树）

(0)
(0)