带修莫队 - CSDN
精华内容
参与话题
  • 带修莫队板子

    2019-11-09 16:27:22
    //一定要记录每次询问前修改了几次 #include<bits/stdc++.h> using namespace std; const int N=1e6; int a[N],cnt[N],ans[N],tot,res,m,n,bl[N],bll,cnum; char op; struct query ...struct ...
    第二天叫醒我的不是闹钟,是梦想!

    //一定要记录每次询问前修改了几次
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e6;
    int a[N],cnt[N],ans[N],tot,res,m,n,bl[N],bll,cnum;
    char op;
    struct query
    {
    int l,r,id,pre;//最近修改的位置
    }e[N];
    struct upadate
    {
    int pos,data;
    }q[N];
    int read()
    {
    int res = 0 ;
    char c = getchar() ;
    while(!isdigit©) c = getchar() ;
    while(isdigit©) res = (res << 1) + (res << 3) + c - 48 , c = getchar() ;
    return res ;
    }
    bool cmp(const query &a,const query &b)
    {
    if(a.l!=b.l) return bl[a.l]<bl[b.l];
    if(a.r!=b.r) return bl[a.r]<bl[b.r];
    return a.pre<b.pre;
    }
    void add(int i)
    {
    if((++cnt[a[i]])==1) res++;
    }
    void remove(int i )
    {
    if((–cnt[a[i]])==0) res–;
    }
    void work(int now,int i)
    {
    if(q[now].pos>=e[i].l&&q[now].pos<=e[i].r)
    {
    if((–cnt[a[q[now].pos]])==0) res–;
    if((++cnt[q[now].data])1) res++;
    }
    swap(a[q[now].pos],q[now].data);
    }
    int main()
    {
    n=read();m=read();
    bll=sqrt(n);
    for(int i=1;i<=n;i++) a[i]=read(),bl[i]=(i-1)/bll+1;
    for(int i=1;i<=m;i++)
    {
    scanf("%c",&op);
    if(op
    ’Q’)
    {
    e[++tot].l=read();
    e[tot].r=read();
    e[tot].pre=cnum;
    e[tot].id=tot;
    }
    else
    {
    q[++cnum].pos=read();
    q[cnum].data=read();
    }
    }
    sort(e+1,e+1+tot,cmp);
    int curR=0,curL=1,now=0;
    res=0;
    for(int i=1;i<=tot;i++)
    {
    int L=e[i].l,R=e[i].r;
    while(curL<L) remove(curL++);
    while(curL>L) add(–curL);
    while(curR<R) add(++curR);
    while(curR>R) remove(curR–);
    while(now<e[i].pre) work(++now,i);//改少了,改过去
    while(now>e[i].pre) work(now–,i);//改多了,改回来
    ans[e[i].id]=res;
    }
    for(int i=1;i<=tot;i++) cout<<ans[i]<<endl;
    }

    展开全文
  • 带修莫队

    2020-09-30 22:23:54
    块大小取n2/3优于取sqrt(n)的情况,总体复杂度O(n5/3)。 大小为pow(n t,1/3) 时间复杂度pow(n n* n *n *t,1/3) #include<cstdio> #include<cstring> #include<iostream>...struc

    块大小取n2/3优于取sqrt(n)的情况,总体复杂度O(n5/3)。
    大小为pow(n t,1/3) 时间复杂度pow(n n* n *n *t,1/3)

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    const int N=1e4+100;
    int a[N];
    struct query{
    	int id,l,r,t;
    }q[N];
    struct modify{
    	int p,c;
    }d[N];
    int cnt[1000010];
    int ans[N];
    int len;
    int get(int x)
    {
    	return x/len;
    }
    bool cmp(query a,query b)
    {
    	int i=get(a.l),j=get(b.l),x=get(a.r),y=get(b.r);
    	if(i!=j) return i<j;
    	if(x!=y) return x<y;
    	return a.t<b.t;
    }
    void add(int x,int &res)
    {
    	if(cnt[x]==0) res++;
    	cnt[x]++;
    }
    void del(int x,int &res)
    {
    	cnt[x]--;
    	if(cnt[x]==0) res--;
    }
    int main()
    {
    	int n,m;
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=n;i++)
    	{
    		scanf("%d",&a[i]);
    	}
    	int cq=0,cd=0;
    	for(int i=1;i<=m;i++)
    	{
    		char op[2];
    		scanf("%s",op);
    		if(op[0]=='Q')
    		{
    			++cq;
    			scanf("%d%d",&q[cq].l,&q[cq].r);
    			q[cq].id=cq;//id是cq不是i 
    			q[cq].t=cd;
    		}
    		else
    		{
    			++cd;
    			scanf("%d%d",&d[cd].p,&d[cd].c);
    		}
    	}
    	len=pow((double)(n*cd),1.0/3.0)+1;//算出来可能为0 
    	sort(q+1,q+cq+1,cmp);
    	for(int k=1,i=0,j=1,ct=0,res=0;k<=cq;k++)
    	{
    		int id=q[k].id,l=q[k].l,r=q[k].r,t=q[k].t;
    		while(j<l) del(a[j++],res);
    		while(j>l) add(a[--j],res);
    		while(i<r) add(a[++i],res);
    		while(i>r) del(a[i--],res);
    		while(ct<t)
    		{
    			++ct;
    			if(d[ct].p>=l&&d[ct].p<=r)
    			{
    				del(a[d[ct].p],res);
    				add(d[ct].c,res);
    			}
    			swap(a[d[ct].p],d[ct].c);
    		}
    		while(ct>t)
    		{
    			
    			if(d[ct].p>=l&&d[ct].p<=r)
    			{
    				del(a[d[ct].p],res);
    				add(d[ct].c,res);
    			}
    			swap(a[d[ct].p],d[ct].c);
    			ct--;
    		}
    		ans[id]=res;
    	}
    	for(int i=1;i<=cq;i++)
    	{
    		printf("%d\n",ans[i]);
    	}
    }
    
    展开全文
  • 题目大意:给出一个长度为 n 的序列 a,sum 为数列 a 的前缀异或和,再给出 m 次操作,每次操作分为两种类型: ...带修莫队模板题,存个板子,对于这个题目而言,转换后的题意如上,因为修改操作

    题目链接:点击查看

    题目大意:给出一个长度为 n 的序列 a,sum 为数列 a 的前缀异或和,再给出 m 次操作,每次操作分为两种类型:

    1. 1 l r:询问 sum 在区间 [ l , r ] 内有多少对不重复的数
    2. 2 pos:交换 a[ pos ] 和 a[ pos + 1 ] 位置的数

    题目分析:参考博客:https://blog.csdn.net/qq_42576687/article/details/98211361

    带修莫队模板题,存个板子,对于这个题目而言,转换后的题意如上,因为修改操作对于前缀异或和的影响只有 pos 位置受到影响,其他位置不受影响,所以可以视为单点修改,询问有多少对不重复的数,正难则反,可以用总数减去区间内有多少对重复的数即可

    分块大小为 \small n^{\frac{2}{3}} ,时间复杂度为 \small n^{\frac{5}{3}}

    相对于普通莫队而言,只是在结构体中多了一个变量 t ,代表当前询问之前有多少次修改,在处理时 while 循环也多了两重,需要放在端点修改的 while 之后

    修改的话需要分类讨论一下,如果当前修改的点位于当前询问的区间内,则需要对区间的贡献同样做出修改,否则的话不用处理

    代码:
     

    #include<iostream>
    #include<cstdio>
    #include<string>
    #include<ctime>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<stack>
    #include<climits>
    #include<queue>
    #include<map>
    #include<set>
    #include<sstream>
    #include<cassert>
    using namespace std;
    
    typedef long long LL;
    
    typedef unsigned long long ull;
    
    const int inf=0x3f3f3f3f;
    
    const int N=1e5+100;
    
    int size,n,m,a[N],sum[N],p[N],qcnt,pcnt;
    
    LL cnt[N*10],ans[N];
    
    struct query
    {
    	int l,r,id,t;
    	bool operator<(const query& a)const
    	{
    		if(l/size!=a.l/size)
    			return l<a.l;
    		else if(r/size!=a.r/size)
    			return r<a.r;
    		else
    			return t<a.t;
    	}
    }q[N];
    
    LL add(int pos)
    {
    	return cnt[sum[pos]]++;
    }
    
    LL del(int pos)
    {
    	return --cnt[sum[pos]];
    }
    
    LL modify(int id,int pos)
    {
    	LL ans=0;
    	bool flag=q[id].l<=p[pos]&&p[pos]<=q[id].r;
    	if(flag)
    		ans-=del(p[pos]);
    	sum[p[pos]]^=a[p[pos]];
    	swap(a[p[pos]],a[p[pos]+1]);
    	sum[p[pos]]^=a[p[pos]];
    	if(flag)
    		ans+=add(p[pos]); 
    	return ans;
    }
    
    void solve()
    {
    	sort(q+1,q+1+qcnt);
    	int l=1,r=0,t=0;
    	LL sum=0;
    	for(int i=1;i<=qcnt;i++)
    	{
    		int ql=q[i].l,qr=q[i].r,qt=q[i].t;
    		while(r<qr)
    			sum+=add(++r);
    		while(l>ql)
    			sum+=add(--l);
    		while(r>qr)
    			sum-=del(r--);
    		while(l<ql)
    			sum-=del(l++);
    		while(t<qt)
    			sum+=modify(i,++t);
    		while(t>qt)
    			sum+=modify(i,t--);
    		ans[q[i].id]=1LL*(qr-ql+1)*(qr-ql)/2-sum;
    	}
    }
    
    int main()
    {
    #ifndef ONLINE_JUDGE
    //  freopen("data.in.txt","r",stdin);
    //  freopen("data.out.txt","w",stdout);
    #endif
    //  ios::sync_with_stdio(false);
    	while(scanf("%d%d",&n,&m)!=EOF)
    	{
    		memset(cnt,0,sizeof(cnt));
    		size=(int)pow(n,2.0/3.0);
    		for(int i=1;i<=n;i++)
    		{
    			scanf("%d",a+i);
    			sum[i]=sum[i-1]^a[i];
    		}
    		qcnt=0,pcnt=0;
    		while(m--)
    		{
    			int op;
    			scanf("%d",&op);
    			if(op==1)
    			{
    				int l,r;
    				scanf("%d%d",&l,&r);
    				qcnt++;
    				q[qcnt].l=l-1,q[qcnt].r=r,q[qcnt].t=pcnt,q[qcnt].id=qcnt;
    			}
    			else
    			{
    				int pos;
    				scanf("%d",&pos);
    				p[++pcnt]=pos;
    			}
    		}
    		solve();
    		for(int i=1;i<=qcnt;i++)
    			printf("%lld\n",ans[i]);
    	}
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
        return 0;
    }

     

    展开全文
  • 莫队 如果知道[l,r]的答案时能快速求出[l+1,r][l,r+1][l-1,r][l,r-1]的答案,那么可以用莫队离线求解 如果要从[l,r]得到[l',r'],那么需要$O(|r'-r|+|l'-l|)$次更新答案 所以需要确定一个求答案的顺序使得这玩意...

    莫队

    如果知道[l,r]的答案时能快速求出[l+1,r][l,r+1][l-1,r][l,r-1]的答案,那么可以用莫队离线求解

    如果要从[l,r]得到[l',r'],那么需要$O(|r'-r|+|l'-l|)$次更新答案

    所以需要确定一个求答案的顺序使得这玩意最优

    以$\frac{n}{q}$分块,按l所在块为第一关键字,r为第二关键字排序

    总复杂度是$O(n \sqrt q)$

    luogu1494 小Z的袜子

    询问$\sum{cnt[i]*(cnt[i]-1)}$,其中cnt[i]是每种颜色出现的次数

    可以发现当$cnt[i]+=d$时,这玩意会$+=d^2+2*cnt[i]*d-d$

    于是记每种颜色出现的次数就好了

     1 #include<bits/stdc++.h>
     2 #define CLR(a,x) memset(a,x,sizeof(a))
     3 using namespace std;
     4 typedef long long ll;
     5 typedef unsigned long long ull;
     6 typedef pair<int,int> pa;
     7 const int maxn=5e4+10;
     8 
     9 inline ll rd(){
    10     ll x=0;char c=getchar();int neg=1;
    11     while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
    12     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    13     return x*neg;
    14 }
    15 
    16 int N,M,col[maxn],cnt[maxn],sqn;
    17 ll ans[maxn],len[maxn];
    18 struct Node{
    19     int l,r,i;
    20 }q[maxn];
    21 
    22 inline bool cmp(Node a,Node b){
    23     return a.l/sqn==b.l/sqn?a.r<b.r:a.l<b.l;
    24 }
    25 
    26 inline ll gcd(ll x,ll y){
    27     if(!x) return y;
    28     return gcd(y%x,x);
    29 }
    30 
    31 int main(){
    32     //freopen("","r",stdin);
    33     int i,j,k;
    34     N=rd(),M=rd();sqn=sqrt(N);
    35     for(i=1;i<=N;i++) col[i]=rd();
    36     for(i=1;i<=M;i++){
    37         q[i].l=rd(),q[i].r=rd(),q[i].i=i;
    38         len[i]=1ll*(q[i].r-q[i].l+1)*(q[i].r-q[i].l);
    39     }
    40     sort(q+1,q+M+1,cmp);
    41     int l=1,r=0;
    42     ll tmp=0;
    43     for(i=1;i<=M;i++){
    44         if(q[i].l==q[i].r) len[q[i].i]=1;
    45         while(r<q[i].r){
    46             tmp+=cnt[col[++r]]*2;
    47             cnt[col[r]]++;
    48         }
    49         while(r>q[i].r){
    50             tmp+=2-cnt[col[r]]*2;
    51             cnt[col[r--]]--;
    52         }
    53         while(l>q[i].l){
    54             tmp+=cnt[col[--l]]*2;
    55             cnt[col[l]]++;
    56         }
    57         while(l<q[i].l){
    58             tmp+=2-cnt[col[l]]*2;
    59             cnt[col[l++]]--;
    60         }
    61         ans[q[i].i]=tmp/gcd(tmp,len[q[i].i]),len[q[i].i]/=gcd(tmp,len[q[i].i]);
    62     }
    63     for(i=1;i<=M;i++){
    64         
    65         printf("%lld/%lld\n",ans[i],len[i]);
    66     }
    67     return 0;
    68 }
    View Code

     

    luogu3709 大爷的字符串题

    描述比较迷,但是分析以后给一个构造就是每次那个区间最少能给他排成几个严格递增的序列,不难发现就是众数的个数

    于是莫队,记$cnt[i]$是$i$出现的次数,$num[j]$是$cnt$为$j$出现的次数,以及目前的最大$cnt$,我这个最大的$cnt$的数量被减没了,就换到原来的最大的$-1$

     1 #include<bits/stdc++.h>
     2 #define CLR(a,x) memset(a,x,sizeof(a))
     3 #define MP make_pair
     4 using namespace std;
     5 typedef long long ll;
     6 typedef unsigned long long ull;
     7 typedef pair<int,int> pa;
     8 const int maxn=2e5+10;
     9 
    10 inline ll rd(){
    11     ll x=0;char c=getchar();int neg=1;
    12     while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
    13     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    14     return x*neg;
    15 }
    16 
    17 int N,NN,M,a[maxn],tmp[maxn];
    18 int ans[maxn],cnt[maxn],num[maxn];
    19 struct Node{
    20     int l,r,i;
    21 }q[maxn];
    22 
    23 inline bool cmp(Node x,Node y){
    24     return x.l/NN==y.l/NN?x.r<y.r:x.l<y.l;
    25 }
    26 
    27 int main(){
    28     //freopen("","r",stdin);
    29     int i,j,k;
    30     N=rd(),M=rd();NN=sqrt(N);
    31     for(i=1;i<=N;i++){
    32         a[i]=tmp[i]=rd();
    33     }sort(tmp+1,tmp+N+1);
    34     j=unique(tmp+1,tmp+N+1)-tmp;
    35     for(i=1;i<=N;i++)
    36         a[i]=lower_bound(tmp+1,tmp+j,a[i])-tmp;
    37     for(i=1;i<=M;i++){
    38         q[i].l=rd(),q[i].r=rd(),q[i].i=i;
    39         ans[i]=0;
    40     }
    41     sort(q+1,q+M+1,cmp);
    42     
    43     int ma=0,l=1,r=0;
    44     for(i=1;i<=M;i++){
    45         while(r<q[i].r){
    46             cnt[a[++r]]++;
    47             num[cnt[a[r]]]++,num[cnt[a[r]]-1]--;
    48             if(cnt[a[r]]>ma) ma=cnt[a[r]];
    49         }while(r>q[i].r){
    50             cnt[a[r]]--;
    51             num[cnt[a[r]]]++,num[cnt[a[r]]+1]--;
    52             if(!num[ma]) ma--;
    53             r--;
    54         }
    55         while(l>q[i].l){
    56             cnt[a[--l]]++;
    57             num[cnt[a[l]]]++,num[cnt[a[l]]-1]--;
    58             if(cnt[a[l]]>ma) ma=cnt[a[l]];
    59         }while(l<q[i].l){
    60             cnt[a[l]]--;
    61             num[cnt[a[l]]]++,num[cnt[a[l]]+1]--;
    62             if(!num[ma]) ma--;
    63             l++;
    64         }
    65         ans[q[i].i]-=ma;
    66     }
    67     for(i=1;i<=M;i++)
    68         printf("%d\n",ans[i]);
    69     return 0;
    70 }
    View Code

     

    树上莫队

    针对树上路径的询问

    欧拉序做法

    考虑一棵树的欧拉序(即括号序,进和出时各记一次),如果对于一个区间,某个元素出现了两次,则认为它没出现过,那么对于路径(a,b)有两种情况(不妨设a在b前面):

    1.$a$或$b$中有一个是$lca$:$[in[a],in[b]]$

    2.否则:$[out[a],in[b]]U\{lca\}$

    画图理解即可

    于是就变成了和普通莫队一样。但需要注意的是这个区间不能拆,所以有一些题做不了...

    树分块做法

    考虑按某种方法对树分块,最后排序时的关键字改为那个点所属的块的编号

    考虑dfs时维护一个栈,进入点x时记下栈中元素个数,每从一个x的子树出来时,判断一下新增的元素个数是否大于$B$(块大小),如果大于的话,把新增的这些点分到同一个块里;出x的时候将x计入栈中。最后剩下的元素扔到最后一个块里

    这样可以保证块大小都是$[B,3B]$的

     1 void dfs(int x){
     2     int t=sh;
     3     for(int i=egh[x];i;i=eg[i][1]){
     4         int b=eg[i][0];if(b==fa[x][0]) continue;
     5         fa[b][0]=x,dep[b]=dep[x]+1;dfs(b);
     6         if(sh-t>=blk){
     7             ++bct;
     8             for(;sh>t;sh--) bel[stk[sh]]=bct;
     9         }
    10     }
    11     stk[++sh]=x;
    12 }

    然后处理询问的时候,要从(a,b)到(c,b),只要考虑(a,c)路径上的点即可

     

    带修莫队

    可以将修改视为第三维来做,复杂度$O\left(\frac{qn^2}{B^2}+qB+\frac{n^2}{B}\right)$,B是块大小

    $n=q$时可以取$B=n^{\frac{2}{3}}$,复杂度是$O(n^{\frac{5}{3}})$

     

    [WC2013]糖果公园

    带修树上莫队

      1 #include<bits/stdc++.h>
      2 #include<tr1/unordered_map>
      3 #define CLR(a,x) memset(a,x,sizeof(a))
      4 #define MP make_pair
      5 #define fi first
      6 #define se second
      7 #define oct hakheaw
      8 using namespace std;
      9 typedef long long ll;
     10 typedef unsigned long long ull;
     11 typedef long double ld;
     12 typedef pair<int,int> pa;
     13 const int maxn=1e5+10,Blk=2154;
     14 
     15 inline ll rd(){
     16     ll x=0;char c=getchar();int neg=1;
     17     while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
     18     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
     19     return x*neg;
     20 }
     21 
     22 struct Node{
     23     int l,r,x,t,i;
     24     Node(int _l=0,int _r=0,int _x=0,int _t=0,int _i=0){l=_l,r=_r,x=_x,t=_t,i=_i;}
     25 }qr[maxn];
     26 int N,M,Q,val[maxn],eg[maxn*2][2],egh[maxn],ect,col[maxn],lik[maxn];
     27 int dfn[maxn][2],tot,id[maxn*2],fa[maxn][20],dep[maxn];
     28 int cg[maxn][3],oct,qct;
     29 int cnt[maxn];
     30 ll ans[maxn];
     31 bool flag[maxn];
     32 inline void adeg(int a,int b){
     33     eg[++ect][0]=b,eg[ect][1]=egh[a],egh[a]=ect;
     34 }
     35 
     36 void dfs(int x){
     37     dfn[x][0]=++tot;id[tot]=x;
     38     for(int i=0;fa[x][i]&&fa[fa[x][i]][i];i++) fa[x][i+1]=fa[fa[x][i]][i];
     39     for(int i=egh[x];i;i=eg[i][1]){
     40         int b=eg[i][0];if(b==fa[x][0]) continue;
     41         fa[b][0]=x;
     42         dep[b]=dep[x]+1;dfs(b);
     43     }
     44     dfn[x][1]=++tot;id[tot]=x;
     45 }
     46 
     47 inline int getlca(int x,int y){
     48     if(dep[x]<dep[y]) swap(x,y);
     49     for(int i=19;i>=0;i--){
     50         if(fa[x][i]&&dep[fa[x][i]]>=dep[y]) x=fa[x][i];
     51     }
     52     if(x==y) return x;
     53     for(int i=19;i>=0;i--){
     54         if(fa[x][i]&&fa[y][i]&&fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
     55     }
     56     return fa[x][0];
     57 }
     58 
     59 inline bool cmp(Node a,Node b){
     60     return (a.l/Blk==b.l/Blk)?((a.r/Blk==b.r/Blk?(a.i<b.i):a.r<b.r)):a.l<b.l;
     61 }
     62 
     63 inline ll inc(int c){
     64     return 1ll*val[c]*lik[++cnt[c]];
     65 }
     66 
     67 inline ll dec(int c){
     68     return -1ll*val[c]*lik[cnt[c]--];
     69 }
     70 
     71 inline ll deal(int x){
     72     // printf("DEAL:%d\n",x);
     73     flag[x]^=1;
     74     if(flag[x]) return inc(col[x]);
     75     else return dec(col[x]);
     76 }
     77 
     78 inline ll change(int x,int y){
     79     ll re=0;
     80     if(flag[x]) re+=dec(col[x])+inc(y); 
     81     // printf("CG:%d %d %d %d\n",x,y,col[x],re);
     82     col[x]=y;
     83     return re;
     84 }
     85 
     86 int main(){
     87     //freopen("","r",stdin);
     88     N=rd(),M=rd(),Q=rd();
     89     for(int i=1;i<=M;i++) val[i]=rd();
     90     for(int i=1;i<=N;i++) lik[i]=rd();
     91     for(int i=1;i<N;i++){
     92         int a=rd(),b=rd();
     93         adeg(a,b),adeg(b,a);
     94     }
     95     for(int i=1;i<=N;i++) col[i]=rd();
     96     dep[1]=1;dfs(1);
     97     // for(int i=1;i<=tot;i++) printf("~%d %d\n",i,id[i]);
     98     for(int i=1;i<=Q;i++){
     99         int a=rd(),b=rd(),c=rd();
    100         if(!a) cg[++oct][0]=b,cg[oct][1]=c,cg[oct][2]=col[b],col[b]=c;
    101         else{
    102             if(dfn[b][0]>dfn[c][0]) swap(b,c);
    103             int lca=getlca(b,c);
    104             if(lca==b) qr[++qct]=Node(dfn[b][0],dfn[c][0],lca,oct,i);
    105             else qr[++qct]=Node(dfn[b][1],dfn[c][0],lca,oct,i);
    106         }
    107     }
    108     sort(qr+1,qr+qct,cmp);
    109     ll now=0;int l=1,r=0,t=oct;
    110     for(int i=1;i<=qct;i++){//if(i==2) continue;
    111         int x=qr[i].l,y=qr[i].r,z=qr[i].t;
    112         while(t<z) ++t,now+=change(cg[t][0],cg[t][1]);
    113         while(t>z) now+=change(cg[t][0],cg[t][2]),t--;
    114         while(r<y) now+=deal(id[++r]);
    115         while(r>y) now+=deal(id[r--]);
    116         while(l<x) now+=deal(id[l++]); 
    117         while(l>x) now+=deal(id[--l]);
    118         ans[qr[i].i]=now;
    119         if(qr[i].x!=id[qr[i].l]) ans[qr[i].i]+=deal(qr[i].x),deal(qr[i].x);
    120     }
    121     for(int i=1;i<=Q;i++) if(ans[i]) printf("%lld\n",ans[i]);
    122     return 0;
    123 }

     

    转载于:https://www.cnblogs.com/Ressed/p/9997453.html

    展开全文
  • 莫队算法+带修莫队+回滚莫队

    万次阅读 多人点赞 2016-07-09 16:24:28
    莫队算法 本质上。。似乎是大暴力。。。 ...传说中能解决一切区间问题的算法 ...如果我们知道区间[L,R][L,R][L,R],就能在比较短的时间内求出[L−1,R],[L+1,R],[L,R−1],[L,R+1][L...有一种经典的问题:给你一些不带修...
  • 学习了莫队,感觉这个算法是一个很玄学的的算法,分块的大小和排序方式就能决定这个算法的效率,现在就对莫队,和带修莫队做一个简单的总结。 适用环境: 莫队算法使用分块的思想,可以解决一类离线区间询问问题...
  • 于是,改进后的莫队——带修莫队就这样产生了。 Link 普通莫队详见博客莫队算法学习笔记(一)——普通莫队 接下来,我们一起在普通莫队的基础之上,学会带修莫队这个强大无比的算法。 ...
  • 哎,很纠结,我刚学这个东西...好,我来尝试讲明白我可能明白的莫队知识。 莫队,通常是用来解决一些区间询问的问题,是一种离线算法。它适用于在知道区间[l,r][l,r][l,r]的答案后能在O(1)O(1)O(1)或者O(logn)O(l...
  • 【BZOJ 2120】带修莫队

    2019-04-16 18:04:31
    裸的带修莫队 带修莫队对莫队来说 主要有几点变化 首先分的块是n^(1.5) 这样总时间复杂度是O(n^(5/3)) 然后解决修改的问题就是加一个时间变量 先解决时间维度 对这次提问 如果在你修改之后 那么你把需要的都修改上 ...
  • 记一个看起来很SB时间复杂度O(n5/3)O(n5/3)O(n^{5/3})连暴力都是O(n2)O(n2)O(n^2)但是有些时候可以代替树套树而且空间非常小而且超好些的高科技算法带修莫队: 修改按时间排序 查询按左端点的块为第一关键字,右端...
  • 莫队 + 带修莫队

    2019-09-27 18:59:41
    莫队其实就是一个优化的暴力,通过将区间询问按一定规则进行排序,从而优化过程,求出答案。 举一例子:(例子不具备权威性,只是让读者了解莫队是干啥的) /* 输入四个区间 1 4 初始条件,L= R = 0...
  • 2120: 数颜色  Time Limit: 6 Sec Memory Limit: 259 MB Description 墨墨购买了一套N支彩色画...
  • 【BZOJ2120】数颜色,带修莫队

    千次阅读 2016-09-08 09:28:44
    翘文科课到机房来_(:зゝ∠)_
  • 4129: Haruna’s Breakfast  Time Limit: 10 Sec Memory Limit: 128 MB Description  Haruna每天都会给提...
  • 莫队可以修改,那不是爆炸了。。解法: 不会莫队看这里 莫队还是原来的莫队。 只是了个修改。 T表示当前进行了几次修改,a[i].t表示第i个询问之前有多少个操作。 如果当前进行的操作次数少于我要修改的次数...
  • 带修莫队裸题啊, 直接暴力搞就是了。 要学习带修莫队我推荐胡小兔的博客,这位大佬写得实在是详细,我都不知道有什么可以补充的。 代码: #include&lt;bits/stdc++.h&gt; using namespace std; #define ll...
  • 考虑莫队的转移 如果当前数字出现过 线段树上把它置成1 对于询问 二分ans 线段树上查 0到ans的和 是不是ans+1 本题就是把它搞到了序列上 了个修改… 麻烦一点 本质上是一样的//By SiriusRen #include #include...
  • 带修莫队 允许离线的带区间修改的操作 将修改操作编号,称为"时间戳" 普通莫队是不能带修改的,我们可以强行让它可以修改 可以强行加上一维时间维,表示这次操作的时间 [l−1,r,time][l−1,r,time][l−1,r,time] ...
  • 学习笔记——带修莫队

    千次阅读 2018-02-25 12:13:21
    下面就介绍一种O(n53)O(n53)O(n^{\frac 5 3})的带修莫队算法。 算法详解 只需要再维护一维表示操作的时间即可 然后我们按照左边界所在块为第一关键字、右边界所在块为第二关键字,操作时间为第三关键字排序 在...
  • 糖果公园 先吃饭去啦! 题意:待补充 思路:待补充 #include "bits/stdc++.h" #define hhh printf("hhh\n") #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) ...typedef pa...
1 2 3 4 5 ... 20
收藏数 7,118
精华内容 2,847
热门标签
关键字:

带修莫队