这个标题似乎有点既视感
这个算法是在 2013 年的集训队论文集中《浅谈数据结构题的几个非经典解法》里面介绍的.
给个 link https://pan.baidu.com/s/1evT3f-Xkd7HGPTgTY7IJBg , 有兴趣的可以自己学习一下.
应用
专门对付强制在线的算法, 当修改之间对答案的贡献互相独立 (这个和 CDQ 一样)(或可以快速合并) 时, 就可以通过套上一个二进制分组的 log 来做到在线.
介绍
比如现在我有一个数据结构题:
1. 添加一个操作: 把 [l,r] 区间中的数加上 x.
2. 询问如果我执行了 [l,r] 区间的操作, pos 这一个点的值会变为多少.
离线做法就直接大力线段树就可以了, 问题不大, 相信大家都会.
那如果强制在线呢?
我们一想可以二进制分组(不然我讲它干什么).
比如当前有 22 个操作, 22=16+4+2
我们对前 16 个操作建立一个线段树, 后面四个建一个, 再后面两个建一个.
有二进制进位时就重构就可以了.
实际运用的时候不用真的建好几颗线段树.
重构就判断要不要 pushup 就可以了.
具体的如果右儿子进位 (塞爆) 了, 自己就也重构就可以了.
例题: UOJ46
- /*
- @Date : 2020-01-14 22:21:04
- @Author : Adscn ([email protected])
- @Link : https://www.cnblogs.com/LLCSBlog
- */
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- #define IL inline
- #define RG register
- #define gi geti<int>()
- #define gl geti<ll>()
- #define gc getchar()
- #define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
- template<typename T>IL bool chkmax(T &x,const T &y){return x<y?x=y,1:0;}
- template<typename T>IL bool chkmin(T &x,const T &y){return x>y?x=y,1:0;}
- template<typename T>
- IL T geti()
- {
- RG T xi=0;
- RG char ch=gc;
- bool f=0;
- while(!isdigit(ch))ch=='-'?f=1:f,ch=gc;
- while(isdigit(ch))xi=xi*10+ch-48,ch=gc;
- return f?-xi:xi;
- }
- template<typename T>
- IL void pi(T k,char ch=0)
- {
- if(k<0)k=-k,putchar('-');
- if(k>=10)pi(k/10);
- putchar(k%10+'0');
- if(ch)putchar(ch);
- }
- const int N=1e5+7;
- int n,m;
- struct node{
- int l,r,a,b;
- node(){}
- node(int L){l=L;r=a=b=0;}
- node(int L,int R,int A,int B){l=L,r=R,a=A,b=B;}
- bool operator <(const node &b)const{return l<b.l;}
- }t[N<<2];
- inline void merge(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){
- merge(a.a,a.b,b.a,b.b);
- return a;
- }
- #define mid ((l+r)>>1)
- #define ls (rt<<1)
- #define rs (rt<<1|1)
- vector<node>s[N<<2];
- inline void pushup(int rt)
- {
- s[rt].clear();
- int len1=s[ls].size(),len2=s[rs].size(),lst=0;
- for(int i=0,j=0;i<len1&&j<len2;)
- {
- int a=s[ls][i].a,b=s[ls][i].b;
- merge(a,b,s[rs][j].a,s[rs][j].b);
- if(s[ls][i].r<=s[rs][j].r){
- s[rt].emplace_back(lst+1,s[ls][i].r,a,b);
- lst=s[ls][i].r;
- if(s[ls][i].r==s[rs][j].r)++j;
- ++i;
- }
- else{
- s[rt].emplace_back(lst+1,s[rs][j].r,a,b);
- lst=s[rs][j].r;
- ++j;
- }
- }
- }
- inline bool modify(int rt,int l,int r,int pos,node a)
- {
- if(l==r){
- if(a.l!=1)s[rt].emplace_back(1,a.l-1,1,0);
- s[rt].push_back(a);
- if(a.r!=n)s[rt].emplace_back(a.r+1,n,1,0);
- return 1;
- }
- if(pos<=mid)return modify(ls,l,mid,pos,a),0;
- else{
- if(modify(rs,mid+1,r,pos,a))pushup(rt);
- return 1;
- }
- }
- inline node query(int rt,int l,int r,int L,int R,int pos)
- {
- // cout<<rt<<""<<l<<" "<<r<<" "<<L<<" "<<R<<endl;
- // if(l>r)return (node){0,0,1,0};
- if(L<=l&&r<=R){
- // for(auto i:s[rt])printf("Rt=%d:%d %d %d %d\n",rt,i.l,i.r,i.a,i.b);
- auto ret=*--upper_bound(s[rt].begin(),s[rt].end(),node(pos));
- // pi(pos,'\n');
- // printf("ret :%d %d %d %d\n",ret.l,ret.r,ret.a,ret.b);
- return ret;
- }
- if(R<=mid)return query(ls,l,mid,L,R,pos);
- if(L>mid)return query(rs,mid+1,r,L,R,pos);
- return query(ls,l,mid,L,R,pos)+query(rs,mid+1,r,L,R,pos);
- }
- int a[N];
- int main(void)
- {
- #ifndef ONLINE_JUDGE
- // File("");
- #endif
- int type=gi;
- n=gi,m=gi;
- for(int i=1;i<=n;++i)a[i]=gi;
- int q=gi,ans=0,cnt=0;
- while(q--){
- int opt=gi,l=gi,r=gi;
- if(type&1)l^=ans,r^=ans;
- if(opt==1){
- int a=gi,b=gi;
- modify(1,1,100000,++cnt,node(l,r,a,b));
- }
- else{
- int pos=gi;
- if(type&1)pos^=ans;
- auto ret=query(1,1,100000,l,r,pos);
- // cout<<ret.a<<" "<<ret.b<<endl;
- pi(ans=(1ll*a[pos]*ret.a+ret.b)%m,'\n');
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3392967.html