@ivorysi 2018-01-02T10:23:27.000000Z 字数 21633 阅读 808

根号类算法学习笔记

笔记

分块

BZOJ 2724 [Violet 6]蒲公英

题面大意：给出n个数m次询问求[L,R]内的众数（取值最小的一个众数），强制在线

题解

我们可以分块
把数组离散化
维护cnt[i][j]是第i个数，前缀j个块里出现的次数
ans[i][j]是第i块到第j个块里出现的众数是谁
然后更新的时候，我们记录下两边零散的数字，用它们去更新众数

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 40005
//#define ivorysi
using namespace std;
typedef long long ll;
int n,m,Q;
int a[MAXN],b[MAXN],bl[205],br[205],S,tot,cnt[MAXN][205],ans[205][205],sum[MAXN];
bool vis[MAXN];
void Init() {
    S=sqrt(n);
    xiaosiji(i,0,n) {
    if(i%S==0) { br[tot]=i-1;bl[++tot]=i;}
    }
    br[tot]=n-1;bl[tot+1]=br[tot+1]=n;
    siji(i,1,tot) {
    int k=bl[i],cur=-1,maxv=-1;
    xiaosiji(j,k,n) sum[a[j]]=0;
    siji(j,i,tot) {
        int t=br[j];
        while(k<=t) {
        int c=++sum[a[k]];
        if(c > maxv) {maxv=c;cur=a[k];}
        else if(c==maxv && a[k]<cur) {cur=a[k];}
        ++k;
        }
        ans[i][j]=cur;
    }
    }
    siji(i,1,tot) {
    xiaosiji(j,0,m) cnt[j][i]=cnt[j][i-1];
    siji(k,bl[i],br[i]) {
        ++cnt[a[k]][i];
    }
    }
}
int Query(int l,int r) {
    if(r-l < 2*S) {
    siji(i,l,r) {
        if(!vis[a[i]]) {vis[a[i]]=1;sum[a[i]]=1;}
        else ++sum[a[i]];
    }
    int cur=-1,maxv=-1;
    siji(i,l,r) {
        if(vis[a[i]]) {
        if(sum[a[i]]>maxv) {maxv=sum[a[i]];cur=a[i];}
        else if(sum[a[i]]==maxv && a[i]<cur) {cur=a[i];}
        vis[a[i]]=0;
        }
    }
    return b[cur];
    }
    int L_id=l/S+1,R_id=r/S+1;
    if(l==bl[L_id]) --L_id;
    if(r==br[R_id]) ++R_id;
    int cur=ans[L_id+1][R_id-1];
    int maxv=cnt[cur][R_id-1]-cnt[cur][L_id];
    siji(i,l,br[L_id]) {
    if(!vis[a[i]]) {vis[a[i]]=1;sum[a[i]]=1;}
    else ++sum[a[i]];
    }
    siji(i,bl[R_id],r) {
    if(!vis[a[i]]) {vis[a[i]]=1;sum[a[i]]=1;}
    else ++sum[a[i]];
    }
    siji(i,l,br[L_id]) {
    if(vis[a[i]]) {
        int c=sum[a[i]]+cnt[a[i]][R_id-1]-cnt[a[i]][L_id];
        if(c>maxv) {cur=a[i];maxv=c;}
        else if(maxv==c && a[i]<cur) {cur=a[i];}
        vis[a[i]]=0;
    }
    }
    siji(i,bl[R_id],r) {
    if(vis[a[i]]) {
        int c=sum[a[i]]+cnt[a[i]][R_id-1]-cnt[a[i]][L_id];
        if(c>maxv) {cur=a[i];maxv=c;}
        else if(maxv==c && a[i]<cur) {cur=a[i];} 
        vis[a[i]]=0;
    }
    }
    return b[cur];
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d%d",&n,&Q);
    xiaosiji(i,0,n) {scanf("%d",&a[i]);b[i]=a[i];}
    sort(b,b+n);
    m=unique(b,b+n)-b;
    xiaosiji(i,0,n) a[i]=lower_bound(b,b+m,a[i])-b;
    Init();
    int l,r;
    int lastans=0;
    siji(i,1,Q) {
    scanf("%d%d",&l,&r);
    l=(l+lastans-1)%n;r=(r+lastans-1)%n;
    if(l>r) swap(l,r);
    printf("%d\n",lastans=Query(l,r));
    lastans%=n;
    }
    return 0;
}

2821: 作诗(Poetize)

Description

神犇SJY虐完HEOI之后给傻×LYD出了一题：SHY是T国的公主，平时的一大爱好是作诗。由于时间紧迫，SHY作完诗
之后还要虐OI，于是SHY找来一篇长度为N的文章，阅读M次，每次只阅读其中连续的一段[l,r]，从这一段中选出一
些汉字构成诗。因为SHY喜欢对偶，所以SHY规定最后选出的每个汉字都必须在[l,r]里出现了正偶数次。而且SHY认
为选出的汉字的种类数（两个一样的汉字称为同一种）越多越好（为了拿到更多的素材！）。于是SHY请LYD安排选
法。LYD这种傻×当然不会了，于是向你请教……问题简述：N个数，M组询问，每次问[l,r]中有多少个数出现正偶
数次。

Input

输入第一行三个整数n、c以及m。表示文章字数、汉字的种类数、要选择M次。第二行有n个整数，每个数Ai在[1, c
]间，代表一个编码为Ai的汉字。接下来m行每行两个整数l和r，设上一个询问的答案为ans(第一个询问时ans=0)，
令L=(l+ans)mod n+1, R=(r+ans)mod n+1，若L>R，交换L和R，则本次询问为[L,R]。

Output

输出共m行，每行一个整数，第i个数表示SHY第i次能选出的汉字的最多种类数。

Sample Input

5 3 5
1 2 2 3 1
0 4
1 2
2 2
2 3
3 5

Sample Output

2
0
0
0
1

HINT

对于100%的数据，1<=n,c,m<=10^5

题解

继续分块的思路，不过空间开的要注意点
ans[i][j]维护第i块到第j块有多少个数出现次数为正偶数
cnt[i][j]表示i这个数在前j块里出现了几次
查询的时候res=ans[L+1][R-1]
如果外面零散的数在[L+1,R-1]这个地方出现过，而且次数为偶数个，我们--res，然后再判断这个数总共出现次数是否合法，如果合法++res

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long ll;
int n,Q,c;
int a[MAXN],sum[MAXN],bl[320],br[320],cnt[MAXN][320],ans[320][320],tot,S;
bool vis[MAXN];
void Init() {
    S=sqrt(n);
    xiaosiji(i,0,n) {
    if(i%S==0) br[tot]=i-1,bl[++tot]=i;
    }
    br[tot]=n-1;bl[tot+1]=br[tot+1]=n;
    siji(i,1,tot) {
    xiaosiji(j,i,n) sum[a[j]]=0;
    int k=bl[i];
    siji(j,i,tot) {
        ans[i][j]=ans[i][j-1];
        while(k<=br[j]) {
        ++sum[a[k]];
        if(sum[a[k]]!=1 && sum[a[k]]%2==1) --ans[i][j];
        else if(sum[a[k]]%2==0) ++ans[i][j];
        ++k;
        }
    }
    }
    siji(i,1,tot) {
    siji(j,1,c) cnt[j][i]=cnt[j][i-1];
    siji(j,bl[i],br[i]) {
        ++cnt[a[j]][i];
    }
    }
}
int Query(int l,int r) {
    int res=0;
    if(r-l<2*S) {
    siji(i,l,r) {
        if(!vis[a[i]]) {vis[a[i]]=1;sum[a[i]]=1;}
        else ++sum[a[i]];
    }
    siji(i,l,r) {
        if(vis[a[i]]) {
        if(sum[a[i]]%2==0) ++res;
        vis[a[i]]=0;
        }
    }
    return res;
    }
    int L_id=l/S+1,R_id=r/S+1;
    if(l==bl[L_id]) --L_id;
    if(r==br[R_id]) ++R_id;
    res=ans[L_id+1][R_id-1];
    siji(i,l,br[L_id]) {
    if(!vis[a[i]]) {vis[a[i]]=1;sum[a[i]]=1;}
    else ++sum[a[i]];
    }
    siji(i,bl[R_id],r) {
    if(!vis[a[i]]) {vis[a[i]]=1;sum[a[i]]=1;}
    else ++sum[a[i]];
    }
    siji(i,l,br[L_id]) {
    if(vis[a[i]]) {
        int c=cnt[a[i]][R_id-1]-cnt[a[i]][L_id];
        if(c>0 && c%2==0) --res;
        c+=sum[a[i]];
        if(c%2==0) ++res;
        vis[a[i]]=0;
    }
    }
    siji(i,bl[R_id],r) {
    if(vis[a[i]]) {
        int c=cnt[a[i]][R_id-1]-cnt[a[i]][L_id];
        if(c>0 && c%2==0) --res;
        c+=sum[a[i]];
        if(c%2==0) ++res;
        vis[a[i]]=0;
    }
    }
    return res;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d%d%d",&n,&c,&Q);
    xiaosiji(i,0,n) {scanf("%d",&a[i]);}
    Init();
    int lastans=0,l,r;
    siji(i,1,Q) {
    scanf("%d%d",&l,&r);
    l=(l+lastans)%n;r=(r+lastans)%n;
    if(l>r) swap(l,r);
    printf("%d\n",lastans=Query(l,r));
    }
    return 0;
}

BZOJ 3343: 教主的魔法

Description

教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为1、2、……、N。
每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R]（1≤L≤R≤N）内的英雄的身高全部加上一个整数W。（虽然L=R时并不符合区间的书写规范，但我们可以认为是单独增加第L（R）个英雄的身高）
CYZ、光哥和ZJQ等人不信教主的邪，于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C，以验证教主的魔法是否真的有效。
WD巨懒，于是他把这个回答的任务交给了你。

Input

第1行为两个整数N、Q。Q为问题数与教主的施法数总和。
第2行有N个正整数，第i个数代表第i个英雄的身高。
第3到第Q+2行每行有一个操作：
（1）若第一个字母为“M”，则紧接着有三个数字L、R、W。表示对闭区间 [L, R] 内所有英雄的身高加上W。
（2）若第一个字母为“A”，则紧接着有三个数字L、R、C。询问闭区间 [L, R] 内有多少英雄的身高大于等于C。

Output

对每个“A”询问输出一行，仅含一个整数，表示闭区间 [L, R] 内身高大于等于C的英雄数。

Sample Input

5 3
1 2 3 4 5
A 1 5 4
M 3 5 1
A 1 5 4

Sample Output

2
3

HINT

【输入输出样例说明】

原先5个英雄身高为1、2、3、4、5，此时[1, 5]间有2个英雄的身高大于等于4。教主施法后变为1、2、4、5、6，此时[1, 5]间有3个英雄的身高大于等于4。

【数据范围】

对30%的数据，N≤1000，Q≤1000。
对100%的数据，N≤1000000，Q≤3000，1≤W≤1000，1≤C≤1,000,000,000。

题解

分块，每次加的时候加标记，然后零散的地方暴力加，重新对每个块进行排序
注意排序的右区间是一个开区间
然后就是如果r-l<2*S，我们可以暴力做，但是这个块有可能覆盖了三个不同的区间，要都进行重新排序

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 1000005
//#define ivorysi
using namespace std;
typedef long long ll;
int n,Q;
char op[10];
int a[MAXN],b[MAXN],bl[1005],br[1005],add[1005],tot,S;
void Init() {
    S=sqrt(n);
    xiaosiji(i,0,n) {
    if(i%S==0) br[tot]=i-1,bl[++tot]=i;
    }
    br[tot]=n-1;bl[tot+1]=br[tot+1]=n;
    siji(i,1,tot) {
    sort(b+bl[i],b+br[i]+1);
    add[i]=0;
    }
}
void add_val(int l,int r,int w) {
    int L=l/S+1,R=r/S+1;
    if(r-l<2*S) {
    siji(i,l,r) a[i]+=w;
    siji(i,L,R) {
        siji(j,bl[i],br[i]) {
        b[j]=a[j];
        }
        sort(b+bl[i],b+br[i]+1);
    }
    return;
    }
    if(l==bl[L]) --L;
    if(r==br[R]) ++R;
    siji(i,L+1,R-1) add[i]+=w;
    if(l<=br[L]) {
    siji(i,l,br[L]) a[i]+=w;
    siji(i,bl[L],br[L]) b[i]=a[i];
    sort(b+bl[L],b+br[L]+1);
    }
    if(bl[R]<=r) {
    siji(i,bl[R],r) a[i]+=w;
    siji(i,bl[R],br[R]) b[i]=a[i];
    sort(b+bl[R],b+br[R]+1);
    }
}
int find(int l,int r,int inc,int val) {
    while(l<r) {
    int mid=(l+r)>>1;
    if(b[mid]+inc<val) l=mid+1;
    else r=mid;
    }
    return r;
}
int query(int l,int r,int c) {
    int res=0;
    int L=l/S+1,R=r/S+1;
    if(r-l < 2*S) {
    siji(i,l,r) {if(a[i]+add[i/S+1] >=c) ++res;}
    return res;
    }
    if(l==bl[L]) --L;
    if(r==br[R]) ++R;
    siji(i,L+1,R-1) {
    res+=br[i]+1-find(bl[i],br[i]+1,add[i],c);
    }
    siji(i,l,br[L]) {
    if(a[i]+add[L]>=c) ++res;
    }
    siji(i,bl[R],r) {
    if(a[i]+add[R]>=c) ++res;
    }
    return res;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d%d",&n,&Q);
    xiaosiji(i,0,n) {scanf("%d",&a[i]);b[i]=a[i];}
    Init();
    int l,r,c;
    siji(i,1,Q) {
    scanf("%s%d%d%d",op,&l,&r,&c);
    if(op[0]=='M') {
        add_val(l-1,r-1,c);
    }
    else {
        printf("%d\n",query(l-1,r-1,c));
    }
    }
    return 0;
}

BZOJ 2453: 维护队列

Description

你小时候玩过弹珠吗？
小朋友A有一些弹珠，A喜欢把它们排成队列，从左到右编号为1到N。为了整个队列鲜艳美观，小朋友想知道某一段连续弹珠中，不同颜色的弹珠有多少。当然，A有时候会依据个人喜好，替换队列中某个弹珠的颜色。但是A还没有学过编程，且觉得头脑风暴太浪费脑力了，所以向你来寻求帮助。

Input

输入文件第一行包含两个整数N和M。
第二行N个整数，表示初始队列中弹珠的颜色。
接下来M行，每行的形式为“Q L R”或“R x c”，“Q L R”表示A想知道从队列第L个弹珠到第R个弹珠中，一共有多少不同颜色的弹珠，“R x c”表示A把x位置上的弹珠换成了c颜色。

Output

对于每个Q操作，输出一行表示询问结果。

Sample Input

2 3
1 2
Q 1 2
R 1 2
Q 1 2

Sample Output

2
1

HINT

对于100%的数据，有1 ≤ N ≤ 10000, 1 ≤ M ≤ 10000，小朋友A不会修改超过1000次，所有颜色均用1到10^6的整数表示。

题解

这道题的思路非常简单
因为数字个数不会超过10000+1000所以我们一次性读入所有输入，离散化一下
然后ans[i][j]表示第i个块到第j个块有多少个数字，cnt[i][j]表示第i个数在前j个块里出现多少个
查询的时候看外面零散的数是否在[L+1,R-1]这个区间里出现过
然后更改，因为更改比较少，ans可以 $O((\frac {\sqrt n}{2})^2)$ 暴力更改
cnt就 $O(\sqrt n)$ 更改

unique忘记打+1了是真的尴尬

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 10005
//#define ivorysi
using namespace std;
typedef long long ll;
struct node {
    int op,l,r;
    int x,c;
}qry[MAXN];
char s[5];
int n,Q,m;
int a[MAXN],S,bl[105],br[105],tot,cnt[MAXN*2][105],ans[105][105],num[MAXN*2],sum[MAXN*2];
bool vis[MAXN*2];
void Init() {
    S=sqrt(n);
    xiaosiji(i,0,n) {
    if(i%S==0) br[tot]=i-1,bl[++tot]=i;
    }
    br[tot]=n-1;bl[tot+1]=br[tot+1]=n;
    siji(i,1,tot) {
    int k=bl[i];
    xiaosiji(j,k,n) sum[a[j]]=0;
    siji(j,i,tot) {
        ans[i][j]=ans[i][j-1];
        while(k<=br[j]) {
        sum[a[k]]++;
        if(sum[a[k]]==1) ++ans[i][j];
        ++k;
        }
    }
    }
    siji(i,1,tot) {
    siji(j,1,m) cnt[j][i]=cnt[j][i-1];
    siji(j,bl[i],br[i]) {
        ++cnt[a[j]][i];
    }
    }
}
void Change(int pos,int c) {
    if(a[pos]==c) return;
    int Q=pos/S+1;
    siji(i,1,Q) {
    siji(j,Q,tot) {
        if(cnt[a[pos]][j]-cnt[a[pos]][i-1]==1) --ans[i][j];
        if(cnt[c][j]-cnt[c][i-1]==0) ++ans[i][j];
    }
    }
    siji(i,Q,tot) {
    --cnt[a[pos]][i];
    ++cnt[c][i];
    }
    a[pos]=c;
}
int Query(int l,int r) {
    int res=0;
    if(r-l < 2*S) {
    siji(i,l,r) {
        if(!vis[a[i]]) {++res;vis[a[i]]=1;}
    }
    siji(i,l,r) vis[a[i]]=0;
    return res;
    }
    int L=l/S+1,R=r/S+1;
    if(l==bl[L]) --L;
    if(r==br[R]) ++R;
    res=ans[L+1][R-1];
    siji(i,l,br[L]) {
    if(cnt[a[i]][R-1]-cnt[a[i]][L]==0 && (!vis[a[i]])) {
        vis[a[i]]=1;
        ++res;
    }
    }
    siji(i,bl[R],r) {
    if(cnt[a[i]][R-1]-cnt[a[i]][L]==0 && (!vis[a[i]])) {
        vis[a[i]]=1;
        ++res;
    }
    }
    siji(i,l,br[L]) vis[a[i]]=0;
    siji(i,bl[R],r) vis[a[i]]=0;
    return res;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d%d",&n,&Q);
    xiaosiji(i,0,n) {scanf("%d",&a[i]);num[i+1]=a[i];}
    int cnt=0;
    siji(i,1,Q) {
    scanf("%s",s);
    if(s[0]=='Q') {
        qry[i].op=1;
        scanf("%d%d",&qry[i].l,&qry[i].r);
    }
    else {
        qry[i].op=2;
        scanf("%d%d",&qry[i].x,&qry[i].c);
        ++cnt;
        num[n+cnt]=qry[i].c;   
    }
    }
    sort(num+1,num+n+cnt+1);
    m=unique(num+1,num+n+cnt+1)-num-1;
    xiaosiji(i,0,n) a[i]=lower_bound(num+1,num+m+1,a[i])-num;
    Init();
    siji(i,1,Q) {
    if(qry[i].op==1) {
        printf("%d\n",Query(qry[i].l-1,qry[i].r-1));
    }
    else {
        qry[i].c=lower_bound(num+1,num+m+1,qry[i].c)-num;
        Change(qry[i].x-1,qry[i].c);
    }
    }
    return 0;
}

块状链表

由于本笔记作者在经历BZOJ 1500 的洗礼后
（自认为）已经熟练掌握平衡树，故跳过

BZOJ 1878: [SDOI2009]HH的项链

Description

HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一
段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一
个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只
好求助睿智的你，来解决这个问题。

Input

第一行：一个整数N，表示项链的长度。
第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。
第三行：一个整数M，表示HH询问的个数。
接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
N ≤ 50000，M ≤ 200000。

Output

M行，每行一个整数，依次表示询问对应的答案。

Sample Input

6
1 2 3 4 3 5
3
1 2
3 5
2 6

Sample Output

2
2
4

题解

这道题是莫队算法，莫队算法的思想很简单，我们只要把这个东西排个序，然后直接做就可以了
适用于
(1)题目允许离线
(2)题目不包含修改
(3)不同询问区间的答案可以通过计算快速得出

这道题我们通过左右移动区间的指针可以直接计算出另一个区间的答案
所以我们把 $l$ 指针分成 $\sqrt n$ 块,每一块的 $r$ 再进行排序
这样的话对于每一个右指针的移动，在块内的右指针总共的移动是 $O(\sqrt n)$ 的，块之间的转换是 $O(n)$ ，一共有 $O(\sqrt n)$ 块
所以复杂度是 $O(n \sqrt n)$

对于左指针的移动，每一个点在块内的移动是 $O(\sqrt n)$ ，块之间的转换也要 $O(\sqrt n)$ 一共有m个询问，如果m，n视为同阶
则复杂度是 $O(n \sqrt n)$

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 50005
#define MAXM 200005
//#define ivorysi
using namespace std;
struct node {
    int l,r,bl,id;
    bool operator < (const node &rhs) const {
        return bl<rhs.bl || (bl==rhs.bl && r<rhs.r);
    }
}qry[MAXM];
int a[MAXN],n,m,S,ans[MAXM],tl,tr,cnt[1000005],tot;
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d",&n);
    S=sqrt(n);
    siji(i,1,n) scanf("%d",&a[i]);
    int l,r;
    scanf("%d",&m);
    siji(i,1,m) {
        scanf("%d%d",&l,&r);
        qry[i].id=i;
        qry[i].l=l;qry[i].r=r;
        qry[i].bl=(l-1)/S+1;
    }
    sort(qry+1,qry+m+1);
    siji(i,1,m) {
        while(tl < qry[i].l) if(!--cnt[a[tl++]]) --tot;
        while(tl > qry[i].l) if(!cnt[a[--tl]]++) ++tot;
        while(tr < qry[i].r) if(!cnt[a[++tr]]++) ++tot;
        while(tr > qry[i].r) if(!--cnt[a[tr--]]) --tot;
        ans[qry[i].id]=tot; 
    }
    siji(i,1,m) {
        printf("%d\n",ans[i]);
    }
}

带修改的莫队

我们要把时间加进去作为第三维
可以证明，块的大小按照 $O(n^{\frac {2}{3}})$ 来分是最优的，这样我一共有 $n^{\frac {1}{3}}$
时间的移动相当于正序推进时间，如果有修改操作就修改，和反序进行时间，如果有修改操作就反演
对于时间的移动，时间的一次移动是 $O(n)$ 的，左右块的搭配一共有 $O(n^{\frac {2}{3}})$ 种，然后总共就是 $O(n^{\frac {5}{3}})$

对于左指针的移动，在块内的移动是 $O(n^{\frac {2}{3}})$ 的，一共有 $m$ 个询问且 $n,m$ 同阶，那么左指针的移动一共就是 $O(n^{\frac {5}{3}})$

对于右指针的移动，在块内的移动是 $O(n^{\frac {2}{3}})$ ,一共有n个点所以一共是 $O(n^{\frac{5}{3}})$
而当右指针要回移的时候，最坏是 $O(n)$ 的，然后由于左端点的取值有 $O(n^{\frac {1}{3}})$ 所以复杂度不超过 $O(n^{\frac {4}{3}})$ 所以右指针最坏是 $O(n^{\frac{5}{3}})$

树上莫队

首先我们要记住一个结论，对于当前的一种情况 $u_1,v_1$ 转移到 $u_2,v_2$
我们先将 $u_1,v_1$ 的lca扣去，然后将 $u_1,u_2$ 路径上除了lca以外的点状态全部取反，然后将 $v_1,v_2$ 路径上除了lca以外的点状态全部取反，得到的就是 $u_2,v_2$ 之间的点没有取lca的情况
证明似乎可以把路径列出来然后用对称差消一下（对称差就是出现偶数次就被消掉）
dfs时把树上的点每S个分成一块，然后运用以上的方法来转移

BZOJ 3052: [wc2013]糖果公园

题面大意：给出一棵树，树上每个点有一种权值，然后给出数组W然后给出一条路径，求这条路径的贡献，贡献是( $N_v$ 表示这个值出现的次数) $\sum_{i=1}^{m}\sum_{j}^{N_v} V_i*W_j$

题解

套用刚才的模板即可

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long ll;
struct node {
    int x,y,bl,br,id;
    bool operator < (const node &rhs)const {
        if(bl!=rhs.bl) return bl<rhs.bl;
        if(br!=rhs.br) return br<rhs.br;
        return id<rhs.id;
    }
}qry[MAXN];
int n,m,Q,tot;
int op[MAXN],A[MAXN],B[MAXN],last[MAXN];
int col[MAXN],tc[MAXN],block_id[MAXN],cnt,S,sum[MAXN];
int que[MAXN],ql,qr;
ll W[MAXN],V[MAXN],ans[MAXN],cur;
int fa[MAXN][20],dep[MAXN];
bool vis[MAXN];
struct data {
    int to,next;
}edge[MAXN*4];
int head[MAXN],sumedge;
void add(int u,int v) {
    edge[++sumedge].to=v;
    edge[sumedge].next=head[u];
    head[u]=sumedge;
}
void dfs(int u) {
    int st=tot;
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].to;
        if(v!=fa[u][0]) {
            dep[v]=dep[u]+1;
            fa[v][0]=u;
            dfs(v);
            if(tot-st>=S) {
                while(tot>st) block_id[que[tot--]]=cnt;
                ++cnt;
            }
        }
    }
    que[++tot]=u;
}
int lca(int a,int b) {
    if(dep[a]<dep[b]) swap(a,b);
    int l=17;
    while(l>=0) {
        if(dep[fa[a][l]]>=dep[b]) a=fa[a][l];
        if(dep[a]==dep[b]) break;
        --l;
    }
    if(a==b) return a;
    l=17;
    while(fa[a][0]!=fa[b][0]) {
        if(fa[a][l]!=fa[b][l]) {
            a=fa[a][l];b=fa[b][l];
        }
        --l;
    }
    return fa[a][0];
}
void Rev(int x) {
    cur-=W[sum[col[x]]]*V[col[x]];
    vis[x] ? --sum[col[x]] : ++sum[col[x]];
    vis[x]=!vis[x];
    cur+=W[sum[col[x]]]*V[col[x]];
}
void solve(int curX,int tarX) {
    int L=lca(curX,tarX);
    while(curX!=L) {Rev(curX);curX=fa[curX][0];}
    while(tarX!=L) {Rev(tarX);tarX=fa[tarX][0];}
}
void Modify(int x,int y) {
    if(!vis[x]) {col[x]=y;return;}
    Rev(x);col[x]=y;Rev(x);
}
void update(int curT,int tarT){
    while(curT<tarT) {
        ++curT;
        if(!op[curT]) Modify(A[curT],B[curT]);
    }
    while(curT>tarT) {
        if(!op[curT]) Modify(A[curT],last[curT]);
        --curT;
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d%d%d",&n,&m,&Q);
    S=pow(n,2.0/3.0);
    siji(i,1,m) {
        scanf("%lld",&V[i]);
    }
    siji(i,1,n) {
        scanf("%lld",&W[i]);
        W[i]+=W[i-1];
    }
    int u,v;
    xiaosiji(i,1,n) {
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    siji(i,1,n) {
        scanf("%d",&col[i]);
        tc[i]=col[i];
    }
    dep[1]=1;cnt=1;
    dfs(1);
    while(tot) block_id[que[tot--]]=cnt;
    siji(j,1,17) {
        siji(i,1,n) {
            fa[i][j]=fa[fa[i][j-1]][j-1];
        }
    }
    siji(i,1,Q) {
        scanf("%d%d%d",&op[i],&A[i],&B[i]);
        if(op[i]) {
            qry[++tot].x=A[i];qry[tot].y=B[i];
            qry[tot].bl=block_id[A[i]];
            qry[tot].br=block_id[B[i]];
            qry[tot].id=i;
        }
        else {
            last[i]=tc[A[i]];tc[A[i]]=B[i];
        }
    }
    sort(qry+1,qry+tot+1);qry[0].x=qry[0].y=1;
    siji(i,1,Q) {
        update(qry[i-1].id,qry[i].id);
        solve(qry[i-1].x,qry[i].x);solve(qry[i-1].y,qry[i].y);
        int L=lca(qry[i].x,qry[i].y);
        Rev(L);ans[qry[i].id]=cur;Rev(L);
    }
    siji(i,1,Q) {
        if(op[i]) printf("%lld\n",ans[i]);
    }
    return 0;
}

2038: [2009国家集训队]小Z的袜子(hose)

Description

作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。

Input

输入文件第一行包含两个正整数N和M。N为袜子的数量，M为小Z所提的询问的数量。接下来一行包含N个正整数Ci，其中Ci表示第i只袜子的颜色，相同的颜色用相同的数字表示。再接下来M行，每行两个正整数L，R表示一个询问。

Output

包含M行，对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1，否则输出的A/B必须为最简分数。（详见样例）

Sample Input

6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6

Sample Output

2/5
0/1
1/1
4/15

【样例解释】

询问1：共C(5,2)=10种可能，其中抽出两个2有1种可能，抽出两个3有3种可能，概率为(1+3)/10=4/10=2/5。
询问2：共C(3,2)=3种可能，无法抽到颜色相同的袜子，概率为0/3=0/1。
询问3：共C(3,2)=3种可能，均为抽出两个3，概率为3/3=1/1。
注：上述C(a, b)表示组合数，组合数C(a, b)等价于在a个不同的物品中选取b个的选取方案数。

【数据规模和约定】

30%的数据中 N,M ≤ 5000；
60%的数据中 N,M ≤ 25000；
100%的数据中 N,M ≤ 50000，1 ≤ L < R ≤ N，Ci ≤ N。

题解

不带修改的莫队，和第一道题差不多
插入一个数要加上和这个数同种类的其余数
删除一个数要减去和这个数同种类的其余数

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long ll;
struct node {
    int l,r,bl,id;
    bool operator < (const node &rhs) const {
        return bl<rhs.bl || (bl==rhs.bl && r<rhs.r);
    }
}qry[MAXN];
int n,m,S,cnt[MAXN],c[MAXN],len[MAXN];
ll ans[MAXN],cnm[MAXN][3];
ll gcd(ll a,ll b) {
    return b==0 ? a : gcd(b,a%b);
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    siji(i,1,n) scanf("%d",&c[i]);
    S=sqrt(n);
    siji(i,1,m) {
        scanf("%d%d",&qry[i].l,&qry[i].r);
        len[i]=qry[i].r-qry[i].l+1;
        qry[i].id=i;
        qry[i].bl=(qry[i].l-1)/S+1;
    }
    cnm[0][0]=cnm[1][0]=cnm[1][1]=1;
    siji(i,2,n) {
        cnm[i][0]=1;
        siji(j,1,2) {
            cnm[i][j]=cnm[i-1][j-1]+cnm[i-1][j];
        }
    }
    sort(qry+1,qry+m+1);
    int ql=1,qr=1;cnt[c[1]]=1;
    ll now=0;
    siji(i,1,m) {
        while(ql > qry[i].l) now+=cnt[c[--ql]]++;
        while(qr < qry[i].r) now+=cnt[c[++qr]]++;
        while(ql < qry[i].l) now-=--cnt[c[ql++]];
        while(qr > qry[i].r) now-=--cnt[c[qr--]];
        ans[qry[i].id]=now;
    }
    siji(i,1,m) {
        if(ans[i]==0) puts("0/1");
        else {
            ll g=gcd(ans[i],cnm[len[i]][2]);
            printf("%lld/%lld\n",ans[i]/g,cnm[len[i]][2]/g);
        }
    }
    return 0;
}

BZOJ 3781: 小B的询问

Description

小B有一个序列，包含N个1~K之间的整数。他一共有M个询问，每个询问给定一个区间[L..R]，求Sigma(c(i)^2)的值,其中i的值从1到K，其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。

Input

第一行，三个整数N、M、K。
第二行，N个整数，表示小B的序列。
接下来的M行，每行两个整数L、R。

Output

M行，每行一个整数，其中第i行的整数表示第i个询问的答案。

Sample Input

6 4 3
1 3 2 1 1 3
1 4
2 6
3 5
5 6

Sample Output

6
9
5
2

HINT

对于全部的数据，1<=N、M、K<=50000

题解

BZOJ总喜欢锁一类算法的基础题……好让我们买号是吗……
这道题莫队思路很简单，就是删除原来个数的平方，加上新个数的平方

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long ll;
struct node {
    int l,r,bl,id;
    bool operator < (const node &rhs) const {
        return bl<rhs.bl || (bl==rhs.bl && r<rhs.r);
    }
}qry[MAXN];
int n,m,k,S,cnt[MAXN],a[MAXN];
ll cur,ans[MAXN];
void move(int curT,int on) {
    cur-=(ll)cnt[a[curT]]*cnt[a[curT]];
    cnt[a[curT]]+=on;
    cur+=(ll)cnt[a[curT]]*cnt[a[curT]];
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d%d%d",&n,&m,&k);
    S=sqrt(n);
    siji(i,1,n) scanf("%d",&a[i]);
    siji(i,1,m) {
        scanf("%d%d",&qry[i].l,&qry[i].r);
        qry[i].bl=(qry[i].l-1)/S+1;
        qry[i].id=i;
    }
    sort(qry+1,qry+m+1);
    int ql=1,qr=1;cnt[a[1]]=1;cur=1;
    siji(i,1,m) {
        while(ql > qry[i].l) {move(ql-1,1);--ql;}
        while(qr < qry[i].r) {move(qr+1,1);++qr;}
        while(ql < qry[i].l) {move(ql,-1);++ql;}
        while(qr > qry[i].r) {move(qr,-1);--qr;}
        ans[qry[i].id]=cur;
    }
    siji(i,1,m) {
        printf("%lld\n",ans[i]);
    } 
    return 0;
}

由于3757不能再被评测了我又找了一道树上莫队做

BZOJ 4129: Haruna’s Breakfast

Description

Haruna每天都会给提督做早餐！这天她发现早饭的食材被调皮的 Shimakaze放到了一棵树上，每个结点都有一样食材，Shimakaze要考验一下她。
每个食材都有一个美味度，Shimakaze会进行两种操作：
1、修改某个结点的食材的美味度。
2、对于某条链，询问这条链的美味度集合中，最小的未出现的自然数是多少。即mex值。
请你帮帮Haruna吧。

Input

第一行包括两个整数n，m，代表树上的结点数(标号为1~n)和操作数。
第二行包括n个整数a1...an，代表每个结点的食材初始的美味度。
接下来n-1行，每行包括两个整数u，v，代表树上的一条边。
接下来m 行，每行包括三个整数
0 u x 代表将结点u的食材的美味度修改为 x。
1 u v 代表询问以u，v 为端点的链的mex值。

Output

对于每次询问，输出该链的mex值。

Sample Input

10 10
1 0 1 0 2 4 4 0 1 0
1 2
2 3
2 4
2 5
1 6
6 7
2 8
3 9
9 10
0 7 14
1 6 6
0 4 9
1 2 2
1 1 8
1 8 3
0 10 9
1 3 5
0 10 0
0 7 7

Sample Output

0
1
2
2
3

HINT

1<=n<=5*10^4
1<=m<=5*10^4
0<=ai<=10^9

题解

我们首先要注意到这样一个事实，值域只有[0,n]大于n的就可以完全不管，对答案没有影响，然后我们用分块维护每个块内的数字有没有出现满，从前往后扫到第一个没满的块，暴力找出最小的数
然后对于询问套用树上莫队的模板即可
每次找最小的数最优是 $O(\sqrt n)$
所以总体复杂度还是 $O(n^{\frac {5}{3}})$

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long ll;
struct node {
    int l,r,bl,br,id;
    bool operator < (const node &rhs) const {
        if(bl!=rhs.bl) return bl<rhs.bl;
        if(br!=rhs.br) return br<rhs.br;
        return id<rhs.id; 
    }
}qry[MAXN];
struct data {
    int to,next;
}edge[MAXN*2];
int head[MAXN],sumedge,rt;
void add(int u,int v) {
    edge[++sumedge].to=v;
    edge[sumedge].next=head[u];
    head[u]=sumedge;
}
int n,m,col[MAXN],tc[MAXN],S,Q;
int que[MAXN],tot,fa[MAXN][20],dep[MAXN],Bnum,block_id[MAXN];
int cnt[MAXN],ans[MAXN];
bool vis[MAXN];
int size[350],sum[350],T,all;
int op[MAXN],A[MAXN],B[MAXN],last[MAXN];
void dfs(int u) {
    int st=tot;
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].to;
        if(v!=fa[u][0]) {
            fa[v][0]=u;
            dep[v]=dep[u]+1;
            dfs(v);
            if(tot-st>=S) {
                while(tot-st>S) block_id[que[tot--]]=Bnum;
                ++Bnum;
            }
        }
    }
    que[++tot]=u;
}
void Rev(int x) {
    if(col[x]<=n) {
        if(vis[x] && (!--cnt[col[x]])) --sum[col[x]/T+1];
        if((!vis[x]) && (!cnt[col[x]]++)) ++sum[col[x]/T+1];
    }
    vis[x]=!vis[x];
}
int lca(int a,int b) {
    if(dep[a]<dep[b]) swap(a,b);
    int l=17;
    while(l>=0) {
        if(dep[fa[a][l]]>=dep[b]) a=fa[a][l];
        if(dep[a]==dep[b]) break;
        --l;
    }
    if(a==b) return a;
    l=17;
    while(fa[a][0]!=fa[b][0]) {
        if(fa[a][l]!=fa[b][l]) {
            a=fa[a][l];
            b=fa[b][l];
        }
        --l;
    }
    return fa[a][0];
}
void solve(int curX,int tarX) {
    int L=lca(curX,tarX);
    while(curX!=L) {Rev(curX);curX=fa[curX][0];}
    while(tarX!=L) {Rev(tarX);tarX=fa[tarX][0];}
}
void Modify(int x,int y) {
    if(!vis[x]) {
        col[x]=y;
        return;
    }
    Rev(x);col[x]=y;Rev(x);
}
void update(int curT,int tarT) {
    while(curT<tarT) {
        ++curT;
        if(!op[curT]) Modify(A[curT],B[curT]);
    }
    while(curT>tarT) {
        if(!op[curT]) Modify(A[curT],last[curT]);
        --curT;
    }
}
int query() {
    siji(i,1,all) {
        if(sum[i]!=size[i]) {
            siji(j,1,size[i]) {
                if(!cnt[T*(i-1)+j-1]) return T*(i-1)+j-1;
            }
        }
    }
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    S=pow(n,2.0/3.0);T=sqrt(n);
    siji(i,0,n) {
        ++size[i/T+1];
    }
    all=n/T+1;
    siji(i,1,n) {scanf("%d",&col[i]);tc[i]=col[i];}
    int u,v;
    xiaosiji(i,1,n) {
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dep[1]=1;Bnum=1;
    dfs(1);
    siji(j,1,17) {
        siji(i,1,n) {
            fa[i][j]=fa[fa[i][j-1]][j-1];
        }
    }
    while(tot) block_id[que[tot--]]=Bnum;
    siji(i,1,m) {
        scanf("%d%d%d",&op[i],&A[i],&B[i]);
        if(op[i]) {
            qry[++Q].l=A[i];qry[Q].r=B[i];
            qry[Q].bl=block_id[A[i]];qry[Q].br=block_id[B[i]];
            qry[Q].id=i;
        }
        else {
            last[i]=tc[A[i]];tc[A[i]]=B[i];
        }
    }
    sort(qry+1,qry+Q+1);
    qry[0].l=1,qry[0].r=1;
    siji(i,1,Q) {
        update(qry[i-1].id,qry[i].id);
        solve(qry[i-1].l,qry[i].l);solve(qry[i-1].r,qry[i].r);
        int L=lca(qry[i].l,qry[i].r);
        Rev(L);
        ans[qry[i].id]=query();
        Rev(L);
    }
    siji(i,1,m) {
        if(op[i]) {
            printf("%d\n",ans[i]);
        }
    }
    return 0;
}

根号类算法学习笔记

分块

BZOJ 2724 [Violet 6]蒲公英

题解

代码

2821: 作诗(Poetize)

Description

Input

Output

Sample Input

Sample Output

HINT

题解

代码

BZOJ 3343: 教主的魔法

Description

Input

Output

Sample Input

Sample Output

HINT

【输入输出样例说明】

【数据范围】

题解

代码

BZOJ 2453: 维护队列

Description

Input

Output

Sample Input

Sample Output

HINT

题解

代码

块状链表

BZOJ 1878: [SDOI2009]HH的项链

Description

Input

Output

Sample Input

Sample Output

题解

代码

带修改的莫队

树上莫队

BZOJ 3052: [wc2013]糖果公园

题解

代码

2038: [2009国家集训队]小Z的袜子(hose)

Description

Input

Output

Sample Input

Sample Output

【样例解释】

【数据规模和约定】

题解

代码

BZOJ 3781: 小B的询问

Description

Input

Output

Sample Input

Sample Output

HINT

题解

代码

由于3757不能再被评测了我又找了一道树上莫队做

BZOJ 4129: Haruna’s Breakfast

Description

Input

Output

Sample Input

Sample Output

HINT

题解

代码

内容目录