%队：忧压的暴力

莫队一般分为以下几大类：

  • 普通莫队

用于不带修改的离线查询，区间信息 \(O(1)\) 或 \(O(能过)\) 扩展.

  • 带修莫队

用于允许离线的带修改区间查询.

  • 树上莫队

把树的欧拉序或dfs序跑出来，然后在跑出的序列上莫队.
是用于树上的莫队（废话

  • 回滚莫队

分为只增和只减两种，用于增加或删除操作中有一个特别难搞但另一个比较滞胀的情况.
然而我暂时不会

另外还有Tricks或能组合使用的套路，这里就把它们单独列出来：

  • 值域分块

顾名思义，对值域进行分块，求答案的时候通过值域上的跳跃进行求解.
其实当初自己看的时候根本不能顾名思义
大概是因为之前做那道Rmq Problem / Mex的时候还没学分块，直接看了值域分块
毕竟二次离线对莫队入门者极其友好，看都不敢看

  • 二次离线

哦，不会（
貌似是lxl毒瘤搞出来的套路？

莫队的时间复杂度主要取决于以下两个操作：

  • 1.分块

分块的大小直接决定了主程序在跑暴力的途中得到的优化程度.
普通莫队一般取\(\sqrt{n}\)，带修看情况取\(\sqrt[3]{nt}\)（理论最优）或\(n^{\frac{2}{3}}\).

  • 2.排序

一般采用左端点块号优先，右端点编号其次.

inline bool cmp(query a,query b)
{
	return (bel[a.l]^bel[b.l])?bel[a.l]

这时普通莫队的复杂度基本已经达到了\(O(n\sqrt{n})\).
然而还有一种玄学优化，奇偶性排序

inline bool cmp(query a,query b)
{
	return (bel[a.l]^bel[b.l])?bel[a.l]b.r);
}

对于奇数块按第二关键字升序排序，偶数块降序排序，这样跑完奇数块上升区又可以顺便下坡跑完偶数块，玄学分析上可以减少一半的运行时间

以下为题目code:

1.P3901 数列找不同

拿来练手的()

#include 
#define ri register int
#define MAXN 1000001
#define G() getchar()
using namespace std;
template inline void r(T &x)
{
	x=0;
	char i=G();
	bool f=1;
	while(!isdigit(i))
	f&=(i!='-'),i=G();
	while(isdigit(i))
	x=(x<<3)+(x<<1)+i-'0',i=G();
	x*=((f<<1)-1);
}
int n,q,bel[MAXN],totb,lenb;
int cnt[MAXN],a[MAXN];
int cl,cr;
int temp;
bool ans[MAXN];
struct query{
	int l,r;
	int ind;
}qr[MAXN];
bool cmp(query a,query b)
{
	return (bel[a.l]^bel[b.l])?bel[a.l]b.r);
}
inline void add(int pos)
{
	if((++cnt[a[pos]])==1)
	temp++;
}
inline void del(int pos)
{
	if(!(--cnt[a[pos]]))
	temp--;
}
int main()
{
	r(n),r(q);
	lenb=sqrt(n);
    totb=ceil((double)n/lenb);
    for(ri i=1;i<=totb;i++)
    for(ri j=(i-1)*lenb+1;j<=i*lenb;j++)
    bel[j]=i;
    for(ri i=1;i<=n;i++)
    r(a[i]);
    for(ri i=1;i<=q;i++)
    {
        qr[i].ind=i;
        r(qr[i].l);
        r(qr[i].r);
    }
    sort(qr+1,qr+q+1,cmp);
    ri tl,tr;
    for(ri i=1;i<=q;i++)
    {
        tl=qr[i].l,tr=qr[i].r;
        while(cltl)
        add(--cl);
        while(crtr)
        del(cr--);
        if(temp==tr-tl+1)
        ans[qr[i].ind]=1;
    }
    for(ri i=1;i<=q;i++)
    printf("%s\n",ans[i]?"Yes":"No");
    return 0;
}

2.P2709 小B的询问

稍微推一下柿子就好了，把完全平方拆开，其实是个裸的莫队()

#include 
#define ri register int
#define MAXN 100001
using namespace std;

#define G() getchar()
template inline void r(T &x)
{
	x=0;
	char in=G();
	bool f=1;
	while(!isdigit(in))
	f&=(in!='-'),in=G();
	while(isdigit(in))
	x=(x<<3)+(x<<1)+in-'0',in=G();
	x*=((f<<1)-1);
}

int n,m,k;
int cl=1,cr;
int a[MAXN];
int ans[MAXN];
int bel[MAXN];
int cnt[MAXN];
int temp;
int totb,lenb;

struct query{
	int l,r;
	int ind;
}qr[MAXN];

inline bool cmp(query a,query b)
{
	return (bel[a.l]^bel[b.l])?bel[a.l]b.r);
}

inline void add(int x)
{
	temp+=(1+2*cnt[a[x]]);
	cnt[a[x]]++;
}

inline void del(int x)
{
	temp-=(2*cnt[a[x]]-1);
	cnt[a[x]]--;
}

int main()
{
	r(n),r(m);
	r(k);
	lenb=sqrt(n);
	totb=ceil((double)n/lenb);
	for(ri i=1;i<=totb;i++)
	for(ri j=(i-1)*lenb+1;j<=i*lenb;j++)
	bel[j]=i;
	for(ri i=1;i<=n;i++)
	r(a[i]);
	for(ri i=1;i<=m;i++)
	{
		qr[i].ind=i;
		r(qr[i].l),r(qr[i].r);
	}
	sort(qr+1,qr+m+1,cmp);
	for(ri i=1;i<=m;i++)
	{
		int L=qr[i].l,R=qr[i].r;
		while(clL)
		add(--cl);
		while(crR)
		del(cr--);
		ans[qr[i].ind]=temp;
	}
	for(ri i=1;i<=m;i++)
	printf("%d\n",ans[i]);
	return 0;
}

3.P1494 小Z的袜子

推柿子，然后发现这也是个裸题 概率在统计的时候算贡献可以降次(什么奇妙说法)，所以这题也裸了

哦对了，这题还教会我一个迭代式的gcd(a,b):

inline int gcd(int a,int b)
{
	if(!b)
	return a;
	while(b^=a^=b^=a%=b);
	return a;
}

#include 
#define ri register int
#define MAXN 1000001
#define int long long
#define g() getchar()
using namespace std;

int n,m;
int cl=1,cr=0;
int totb,lenb;
int a[MAXN];
int ans1[MAXN],ans2[MAXN];
int temp1,temp2;
int cnt[MAXN];
int bel[MAXN];

inline int gcd(int a,int b)
{
	if(!b)
	return a;
	while(b^=a^=b^=a%=b);
	return a;
}

template inline void r(T &x)
{
	x=0;
	char in=g();
	bool f=1;
	while(!isdigit(in))
	f&=(in!='-'),in=g();
	while(isdigit(in))
	x=(x<<3)+(x<<1)+in-'0',in=g();
	x*=((f<<1)-1);
}

struct query{
	int l,r;
	int ind;
}qr[MAXN];

inline bool cmp(query a,query b)
{
	return (bel[a.l]^bel[b.l])?bel[a.l]b.r);
}

inline void add(int x)
{
	//temp2+=(len<<1);
	temp1+=(cnt[a[x]]<<1);
	cnt[a[x]]++;
}

inline void del(int x)
{
	//temp2+=(2-(len<<1));
	temp1+=(2-(cnt[a[x]]<<1));
	cnt[a[x]]--;
}

inline void calc(int a,int b,int ind)
{
	if(a==0)
	b=1,ans1[ind]=0,ans2[ind]=1;
	else
	{
		int temp=gcd(a,b);
//		cout<<"a="<L)
		add(--cl);
		while(crR)
		del(cr--);
		if(L==R)
		calc(0,1,qr[i].ind);
		else
		calc(temp1,(cr-cl+1)*(cr-cl),qr[i].ind);
	}
	for(ri i=1;i<=m;i++)
	printf("%d/%d\n",ans1[i],ans2[i]);
	return 0;
}

4.T213452 Epsilon in SwI

跟上一题可以说是一模一样，只需要稍微推一下积分展开就行了
完全没有难度

另外，这题说是要离散化，但是写的随机数据太拉了不离散化甚至更快()

哎，麻乐，还是推下柿子罢

\[\frac{2}{r^2-l^2}\epsilon(l,r)\int_l^r(\sum_{i=1}^{maxa}cnt[i]^2x)dx \]

这一大坨看起来很恐怖，但是只要你懂一点点定积分你就会看出:

\[\int_l^r(\sum_{i=1}^{maxa}cnt[i]^2x)dx=\frac{\sum_{i=1}^{maxa}cnt[i]^2}{2}(r^2-l^2) \]

然后出题人很贴心地把系数整了个

\[\frac{2}{r^2-l^2} \]

那这不就裸了吗？
所以答案是：

\[\epsilon(l,r)\sum_{i=1}^{maxa}cnt[i]^2 \]

，这时候你会发现这其实是一道\(\texttt{小Z的妹子}\)，于是就裸了。

//Epsilon in SwI  
//std code  
//by Neutralized.
//2021.11.28 11:13

#include
#define ri register int
#define int long long
#define MAXN 1000001
#define g() getchar()
using namespace std;

int n,m;
int a[MAXN],b[MAXN];
int cnt[MAXN];
int ans1[MAXN],ans2[MAXN];
int bel[MAXN];
int totb,lenb;
int temp1,temp2;

template inline void r(T &x)
{
	x=0;
	char in=g();
	bool f=1;
	while(!isdigit(in))
	f&=(in!='-'),in=g();
	while(isdigit(in))
	x=(x<<3)+(x<<1)+(in^48),in=g();
	x*=((f<<1)-1);
}

inline int gcd(int a,int b)
{
	if(!b)
	return a;
	while(b^=a^=b^=a%=b);
	return a;
}

struct query{
	int l,r;
	int ind;
}qr[MAXN];

inline bool cmp(query a,query b)
{
	return (bel[a.l]^bel[b.l])?bel[a.l]b.r);
}

inline void add(int x)
{
	temp1+=3*cnt[a[x]]*cnt[a[x]]-3*cnt[a[x]];
	temp2+=(cnt[a[x]]<<1)+1;
	cnt[a[x]]++;
}

inline void del(int x)
{
	temp1+=9*cnt[a[x]]-6-3*cnt[a[x]]*cnt[a[x]];
	temp2+=1-(cnt[a[x]]<<1);
	cnt[a[x]]--;
}

inline void calc(int a,int b,int ind)
{
	if(!a)
	ans1[ind]=0,ans2[ind]=1;
	else
	{
		int temp=gcd(a,b);
		a/=temp,b/=temp;
		ans1[ind]=a,ans2[ind]=b;
	}
}

signed main()
{
	ri cl=1,cr=0;
	ri lef,rig;
	r(n),r(m);
	lenb=sqrt(n);
	totb=ceil((double)n/lenb);
	for(ri i=1;i<=totb;i++)
	for(ri j=(i-1)*lenb+1;j<=i*lenb;j++)
	bel[j]=i;
	for(ri i=1;i<=n;i++)
	r(a[i]),b[i]=a[i];
	sort(b+1,b+n+1);
	ri len=unique(b+1,b+n+1)-b-1;
	for(ri i=1;i<=n;i++)
	a[i]=lower_bound(b+1,b+len+1,a[i])-b;
	for(ri i=1;i<=m;i++)
	r(qr[i].l),r(qr[i].r),qr[i].ind=i;
	sort(qr+1,qr+m+1,cmp);
	for(ri i=1;i<=m;i++)
	{
		lef=qr[i].l,rig=qr[i].r;
		while(cllef)
		add(--cl);
		while(crrig)
		del(cr--);
		if(lef==rig)
		calc(0,1,qr[i].ind);
		else
		calc(temp1*temp2,(cr-cl+1)*(cr-cl)*(cr-cl-1),qr[i].ind);
	}
	for(ri i=1;i<=m;i++)
	printf("%lld/%lld\n",ans1[i],ans2[i]);
	return 0;
}

5.P3709 大爷的字符串题

  • 区间众数球阀:
    用num[x]表示出现了x次的数个数，cnt[x]表示x的出现次数
    莫队转移的时候注意一下就行了.

这题卡了我1h 因为有一行忘打了，囸

#include 
#define ri register int
#define int long long
#define MAXN 1000001
using namespace std;

#define G() getchar()
template inline void r(T &x)
{
	x=0;
	char in=G();
	bool f=1;
	while(!isdigit(in))
	f&=(in!='-'),in=G();
	while(isdigit(in))
	x=(x<<3)+(x<<1)+in-'0',in=G();
	x*=((f<<1)-1);
}

int n,m,k;
int cl=1,cr;
int a[MAXN];
int b[MAXN];
int ans[MAXN];
int bel[MAXN];
int cnt[MAXN];
int num[MAXN];
int temp;
int totb,lenb;

struct query{
	int l,r;
	int ind;
}qr[MAXN];

inline bool cmp(query a,query b)
{
	return (bel[a.l]^bel[b.l])?bel[a.l]b.r);
}

inline void add(int x)
{
	num[cnt[a[x]]]--;
	num[++cnt[a[x]]]++;
	temp=max(temp,cnt[a[x]]);
}

inline void del(int x)
{
	//unfinished
	//10 pts
	num[cnt[a[x]]]--;
	if(cnt[a[x]]==temp&&!num[cnt[a[x]]])
	temp--;
	num[--cnt[a[x]]]++; //我日 加这一行就过了 
}

signed main()
{
	r(n),r(m);
	lenb=sqrt(n);
	totb=ceil((double)n/lenb);
	for(ri i=1;i<=totb;i++)
	for(ri j=(i-1)*lenb+1;j<=i*lenb;j++)
	bel[j]=i;
	for(ri i=1;i<=n;i++)
	r(a[i]),b[i]=a[i];
	sort(b+1,b+n+1);
	ri len=unique(b+1,b+n+1)-b-1;
	for(ri i=1;i<=n;i++)
	a[i]=lower_bound(b+1,b+len+1,a[i])-b;
	for(ri i=1;i<=m;i++)
	{
		qr[i].ind=i;
		r(qr[i].l),r(qr[i].r);
	}
	sort(qr+1,qr+m+1,cmp);
	for(ri i=1;i<=m;i++)
	{
		int L=qr[i].l,R=qr[i].r;
		while(clL)
		add(--cl);
		while(crR)
		del(cr--);
		ans[qr[i].ind]=temp;
	}
	for(ri i=1;i<=m;i++)
	printf("%lld\n",-ans[i]);
	return 0;
}

6.P4137 Rmq Problem / mex

这题引入了一个新知识：

\[\color{cornflowerblue}{\small\texttt{Range Partitioning}} \]

\[\color{cornflowerblue}{\texttt{值域分块}} \]

所谓值域分块，就是把出现在题目值域中的值进行分块处理，可以帮你把暴力卡过去 可以实现某些点快得飞起()
具体见代码

#include 
#define ri register int
#define MAXN 300001
#define g() getchar()
#define pc(a) putchar(a)
#define Tp template
using namespace std;
const int inf=0x3f3f3f3f;
const int len=448;

namespace SlowIO
{
	Tp inline void rd(T &x)	{
		x=0;char i=g();bool f=1;
		while(!isdigit(i)) f&=(i!='-'),i=g();
		while(isdigit(i)) x=(x<<3)+(x<<1)+(i^48),i=g();
		x*=((f<<1)-1);
		}
	Tp inline void op(T x){
		if(x<0) pc('-'),x=-x;
		if(x>=10) op(x/10);
		pc(x%10+48);
		}
	Tp inline void writeln(T x){op(x);pc('\n');}
	Tp inline void writesp(T x){op(x);pc(' ');}
	Tp inline void writespf(T x){pc(' ');op(x);}
};
using namespace SlowIO;

int n,m;
int cl,cr;
int a[MAXN];
int num[MAXN];
int cnt[MAXN];
int L[MAXN],R[MAXN];
int ans[MAXN];
int bel[MAXN];

struct query{
    int l,r;
    int ind;
}qr[MAXN];

inline bool cmp(query a,query b)
{
    return (bel[a.l]^bel[b.l])?bel[a.l]b.r);
}

inline void initt()
{
    //值域分块
    for(ri i=1;i<=2e5;i++)
    bel[i]=(i-1)/len+1,L[i]=(i-1)*len+1,R[i]=i*len;
}

inline void add(int x)
{
    if(!cnt[a[x]])
    num[bel[a[x]]]++;
    cnt[a[x]]++;
}

inline void del(int x)
{
    if(cnt[a[x]]==1)
    num[bel[a[x]]]--;
    cnt[a[x]]--;
}

inline int gtans()
{
    if(!cnt[0])
    return 0;
    int ind=1;
    while(num[ind]==len) ind++;
    for(ri i=L[ind];i<=R[ind];i++)
    if(!cnt[i]) return i;
}
#define VSC Shimokitazawa
int main()
{
    rd(n),rd(m);
    initt();
    for(ri i=1;i<=n;i++)
    rd(a[i]);
    for(ri i=1;i<=m;i++)
    rd(qr[i].l),rd(qr[i].r),qr[i].ind=i;
    sort(qr+1,qr+m+1,cmp);
    // cl=qr[1].l+1,cr=qr[1].l;
    cl=1,cr=0;
    //test!
    for(ri i=1;i<=m;i++)
    {
        int tl=qr[i].l,tr=qr[i].r;
        while(cltl)
        add(--cl);
        while(crtr)
        del(cr--);
        ans[qr[i].ind]=gtans();
    }
    for(ri i=1;i<=m;i++)
    writeln(ans[i]);
    #ifdef VSC
    system("pause");
    #endif
    return 0;
}

7.P4396 [AHOI2013]作业

这题需要一个旧知识：

\[\color{cornflowerblue}{\small\texttt{Range Partitioning}} \]

\[\color{cornflowerblue}{\texttt{值域分块}} \]

草，针灸蒯过来不准备删呗

对于task 1和task 2分别处理即可
注意统计的时候可以搞一点加速，帮你踩一堆人

#include 
#define ri register int
#define MAXN 300001
#define g() getchar()
#define pc(a) putchar(a)
#define Tp template
using namespace std;
const int inf=0x3f3f3f3f;
const int len=317;

namespace SlowIO
{
	Tp inline void rd(T &x)	{
		x=0;char i=g();bool f=1;
		while(!isdigit(i)) f&=(i!='-'),i=g();
		while(isdigit(i)) x=(x<<3)+(x<<1)+(i^48),i=g();
		x*=((f<<1)-1);
		}
	Tp inline void op(T x){
		if(x<0) pc('-'),x=-x;
		if(x>=10) op(x/10);
		pc(x%10+48);
		}
	Tp inline void writeln(T x){op(x);pc('\n');}
	Tp inline void writesp(T x){op(x);pc(' ');}
	Tp inline void writespf(T x){pc(' ');op(x);}
};
using namespace SlowIO;

struct query{
    int l,r;
    int a,b;
    int ind;
}qr[MAXN];

int n,m;
int cl,cr;
int a[MAXN];
int cnt[MAXN];
int num[MAXN];
int sum[MAXN];
int L[MAXN],R[MAXN],bel[MAXN];
pair ans[MAXN];

inline bool cmp(query a,query b)
{
    return (bel[a.l]^bel[b.l])?bel[a.l]b.r);
}

inline void initt()
{
    //值域分块
    for(ri i=1;i<=1e5;i++)
    bel[i]=(i-1)/len+1,L[i]=(i-1)*len+1,R[i]=i*len;
}

inline void add(int x)
{
    if(!cnt[a[x]])
    num[bel[a[x]]]++;
    cnt[a[x]]++;
    sum[bel[a[x]]]++;
}

inline void del(int x)
{
    if(cnt[a[x]]==1)
    num[bel[a[x]]]--;
    cnt[a[x]]--;
    sum[bel[a[x]]]--;
}

inline pair gtans(int a,int b)
{
    int ans1=0,ans2=0;
    if(bel[a]==bel[b])
    {
        for(ri i=a;i<=b;i++)
            if(cnt[i]>0) ans2++,ans1+=cnt[i];
    }
    else
    {
        int ind=1,temp;//这里写复杂了一点,可以去看文件夹里的小优化版本,会快22ms
        while(L[ind]b) break;
            ans1+=sum[temp],ans2+=num[temp];
        }
        temp--;
        for(ri i=a;i0) ans2++,ans1+=cnt[i];
        for(ri i=R[temp]+1;i<=b;i++)//这里记得R[temp]+1,因为R[temp]在距离b最近的上一块里(temp)已经计算过了,但不加你谷水数据还能放过去66pts
        if(cnt[i]>0) ans2++,ans1+=cnt[i];
    }
    return make_pair(ans1,ans2);
}
#define VSC Shimokitazawa
int main()
{
	rd(n),rd(m);
    initt();
	for(ri i=1;i<=n;i++)
	rd(a[i]);
    for(ri i=1;i<=m;i++)
    {
        rd(qr[i].l),rd(qr[i].r);
        rd(qr[i].a),rd(qr[i].b);
        qr[i].ind=i;
    }
    sort(qr+1,qr+m+1,cmp);
    cl=1;
    for(ri i=1;i<=m;i++)
    {
        int tl=qr[i].l,tr=qr[i].r;
        while(cl>tl)
        add(--cl);
        while(cltr)
        del(cr--);
        ans[qr[i].ind]=gtans(qr[i].a,qr[i].b);
    }
    for(ri i=1;i<=m;i++)
    writesp(ans[i].first),writeln(ans[i].second);
    #ifdef VSC
    system("pause");
    #endif
	return 0;
}
//好耶

8.P3730 曼哈顿交易

这题还是值域分块.
这里问的是求静态区间第k小，而且tag也有莫队，所以用莫队+值域分块解决.
需要离散化.

#include 
#define ri register int
#define MAXN 1000001
#define g() getchar()
#define pc(a) putchar(a)
#define Tp template
using namespace std;
const int inf=0x3f3f3f3f;
const int len=317;

namespace SlowIO
{
	Tp void rd(T &x)	{
		x=0;char i=g();bool f=1;
		while(!isdigit(i)) f&=(i!='-'),i=g();
		while(isdigit(i)) x=(x<<3)+(x<<1)+(i^48),i=g();
		x*=((f<<1)-1);
	}
	Tp inline void op(T x){
		if(x<0) pc('-'),x=-x;
		if(x>=10) op(x/10);
		pc(x%10+48);
	}
	Tp inline void writeln(T x){op(x);pc('\n');}
	Tp void writesp(T x){op(x);pc(' ');}
};
using namespace SlowIO;

int n,m;
int b[MAXN];
int a[MAXN];
int cnt[MAXN],num[MAXN];
int tot[MAXN];
int bel[MAXN],L[MAXN],R[MAXN];
int cl=1,cr;
int tl,tr;
int temp;
int ans[MAXN];

struct query{
	int l,r;
	int k;
	int ind;
}qr[MAXN];

inline bool cmp(query a,query b)
{
    return (bel[a.l]^bel[b.l])?bel[a.l]b.r);
}

inline void add(int x)
{
    if(!cnt[a[x]])
    temp++;
    else
    {
        num[bel[cnt[a[x]]]]--;
        tot[cnt[a[x]]]--;
    }
    cnt[a[x]]++;
    num[bel[cnt[a[x]]]]++;
    tot[cnt[a[x]]]++;
}

inline void del(int x)
{
    tot[cnt[a[x]]]--;
    num[bel[cnt[a[x]]]]--;
    cnt[a[x]]--;
    if(!cnt[a[x]])
    temp--;
    else
    tot[cnt[a[x]]]++,num[bel[cnt[a[x]]]]++;
}

inline void initt()
{
    //range partitioning
    for(ri i=1;i<=1e5;i++)
    bel[i]=(i-1)/len+1,L[i]=(i-1)*len+1,R[i]=i*len;
}

inline int gtans(int k)
{
    if(temp0) k-=num[top++];
    for(ri i=L[top];i<=R[top];i++)
    {
        if(tot[i]>0) k-=tot[i];
        if(k<=0)
        return i;
    }
}

int main()
{
    rd(n),rd(m);
    initt();
    for(ri i=1;i<=n;i++)
    rd(a[i]),b[i]=a[i];
    sort(b+1,b+n+1);
    int lent=unique(b+1,b+n+1)-b-1;
    for(ri i=1;i<=n;i++)
    a[i]=lower_bound(b+1,b+lent+1,a[i])-b;
    for(ri i=1;i<=m;i++)
    rd(qr[i].l),rd(qr[i].r),rd(qr[i].k),qr[i].ind=i;
    sort(qr+1,qr+m+1,cmp);
    for(ri i=1;i<=m;i++)
    {
        tl=qr[i].l,tr=qr[i].r;
        while(cl>tl)
        add(--cl);
        while(cltr)
        del(cr--);
        ans[qr[i].ind]=gtans(qr[i].k);
    }
    for(ri i=1;i<=m;i++)
    writeln(ans[i]);
    return 0;
}

9.P4867 Gty的二逼妹子序列

一看，值域上的询问
所以直接上值域分块，然后膜队
设计莫队的转移尽量使每次转移复杂度小，最后算答案稍微复杂一点不会有太大影响

#include 
#define ri register int
#define MAXN 1000001
#define g() getchar()
#define pc(a) putchar(a)
#define Tp template
using namespace std;
const int inf=0x3f3f3f3f;
const int len=317;

namespace SlowIO
{
	Tp inline void rd(T &x)	{
		x=0;char i=g();bool f=1;
		while(!isdigit(i)) f&=(i!='-'),i=g();
		while(isdigit(i)) x=(x<<3)+(x<<1)+(i^48),i=g();
		x*=((f<<1)-1);
	}
	Tp inline void op(T x){
		if(x<0) pc('-'),x=-x;
		if(x>=10) op(x/10);
		pc(x%10+48);
	}
	Tp inline void writeln(T x){op(x);pc('\n');}
	Tp inline void writesp(T x){op(x);pc(' ');}
};
using namespace SlowIO;

int n,m;
int cl=1,cr;
int a[MAXN];
int num[MAXN],cnt[MAXN];
int ans[MAXN];

#define bel(a) (a-1)/len+1
#define L(a) (a-1)*len+1
#define R(a) (a*len)

struct query{
	int l,r;
	int a,b;
	int ind;
}qr[MAXN];

inline bool cmp(query a,query b){
	return (bel(a.l)^bel(b.l))?bel(a.l)b.r);
}

inline void add(int x)
{
	if(!cnt[a[x]])
	num[bel(a[x])]++;
	cnt[a[x]]++;
}

inline void del(int x)
{
	if(cnt[a[x]]==1)
	num[bel(a[x])]--;
	cnt[a[x]]--;
}

int gtans(int a,int b)
{
	int ans1=0;
	if(bel(a)==bel(b))
	{
		for(ri i=a;i<=b;i++)
		if(cnt[i]>0) ans1++;
	}
	else
	{
		int ind=(L(bel(a))==a?bel(a):bel(a)+1),temp;
		for(temp=ind;true;temp++)
		if(R(temp)>b) break;
		else ans1+=num[temp];
		temp--;
		for(ri i=a;i0) ans1++;
		for(ri i=R(temp)+1;i<=b;i++)
		if(cnt[i]>0) ans1++;
	}
	return ans1;
}

int main()
{
	rd(n),rd(m);
	for(ri i=1;i<=n;i++)
	rd(a[i]);
	for(ri i=1;i<=m;i++)
	rd(qr[i].l),rd(qr[i].r),rd(qr[i].a),rd(qr[i].b),qr[i].ind=i;
	sort(qr+1,qr+m+1,cmp);
	static int tl,tr;
	for(ri i=1;i<=m;i++)
	{
		tl=qr[i].l,tr=qr[i].r;
		while(cl>tl)
		add(--cl);
		while(cltr)
		del(cr--);
		ans[qr[i].ind]=gtans(qr[i].a,qr[i].b);
	}
	for(ri i=1;i<=m;i++)
	writeln(ans[i]);
    return 0;
}

10.P4462 异或序列

摘自Strange_S的题解：

首先异或和满足前缀，也就是说设sum[i]为a[1]^a[2]^...^a[i] ，那么a[i]^a[i+1]^...^a[j]=sum[j]^sum[i-1]
而且异或不仅满足交换律，而且对于a^b=c时，a^c=b，b^c=a这两个式子同样成立
那么就好做了，假设当前i到j这个子串的异或和为k，就说明sum[j]^sum[i-1]=k，也就是sum[i-1]^k=sum[j]，sum[j]^k=sum[i-1]
然后在区间转移的时候，设cnt[i]为当前区间值为i的前缀有多少个，然后对于增加序列长度的操作，假设新加的位置为r+1，我们先将cnt[sum[r+1]]++，然后求出ans+=cnt[sum[r+1]^k]，左边扩展也是如此，不过注意，向左扩展时，对ans的更新是用sum[l-1]的，因为是sum[j]与sum[i-1]可以满足前缀
而且向右扩展的时候，如果sum[r+1]^k=sum[l-1]的话，ans++，因为我们更新的时候没有计算[l...r+1]区间的影响，所以要维护一下
而对于区间缩小的情况，就ans先减，再更新cnt，因为要先消除贡献再减cnt，其它步骤类似就好了

一句话，利用异或的前缀性和自反性，可以导出转移.
因为年代久远忘了所以直接看code

#include 
#define ri register int
#define MAXN 1000001
#define g() getchar()
#define pc(a) putchar(a)
#define Tp template
using namespace std;
const int inf=0x3f3f3f3f;
int len;

namespace SlowIO
{
	Tp inline void rd(T &x)	{
		x=0;char i=g();bool f=1;
		while(!isdigit(i)) f&=(i!='-'),i=g();
		while(isdigit(i)) x=(x<<3)+(x<<1)+(i^48),i=g();
		x*=((f<<1)-1);
	}
	Tp inline void op(T x){
		if(x<0) pc('-'),x=-x;
		if(x>=10) op(x/10);
		pc(x%10+48);
	}
	Tp inline void writeln(T x){op(x);pc('\n');}
	Tp inline void writesp(T x){op(x);pc(' ');}
};
using namespace SlowIO;

int n,m,k;
int totb;
int a[MAXN];
int pxor[MAXN];
int cnt[MAXN];
int bel[MAXN];
int cl,cr;
int temp;
int ans[MAXN];

struct query{
	int l,r;
	int k;
	int ind;
}qr[MAXN];

inline bool cmp(query a,query b)
{
    return (bel[a.l]^bel[b.l])?bel[a.l]b.r);
}

inline void add(int x)
{
    temp+=cnt[pxor[x]^k];
    cnt[pxor[x]]++;
}

inline void del(int x)
{
    cnt[pxor[x]]--;
    temp-=cnt[pxor[x]^k];
}

inline void initt()
{
    //pre
    len=sqrt(n);
    totb=ceil((double)n/len);
    for(ri i=1;i<=totb;i++)
    for(ri j=(i-1)*len+1;j<=i*len;j++)
    bel[j]=i;
}

int main()
{
    ri tl,tr;
    rd(n),rd(m),rd(k);
    initt();
    cnt[0]=1;
    for(ri i=1;i<=n;i++)
    rd(a[i]),pxor[i]=(pxor[i-1]^a[i]);
    for(ri i=1;i<=m;i++)
    rd(qr[i].l),qr[i].l--,rd(qr[i].r),qr[i].ind=i;
    //在[l,r]上使用前缀XOR应该包含[l-1,r]这一段
    //XOR(i=l -> r) ai=XOR(i=1 -> l-1) ai (xor) XOR(i=1 -> r) ai
    sort(qr+1,qr+m+1,cmp);
    for(ri i=1;i<=m;i++)
    {
        tl=qr[i].l,tr=qr[i].r;
        while(cl>tl)
        add(--cl);
        while(cltr)
        del(cr--);
        ans[qr[i].ind]=temp;
    }
    for(ri i=1;i<=m;i++)
    writeln(ans[i]);
    return 0;
}

\[\color{cornflowerblue}{\huge\texttt{to be continued......}} \]

OI莫队整理集合数据结构

相关

数据结构--栈（C语言实现）

[NOIP2016] 天天爱跑步

scala future 动态并行异步 ;promise jobs join item scala dynamic

应用监控利器：Pinpoint 全链路监控部署实践

FILECOIN区块奖励机制

unity 链接 Android手机profile

【莫队算法】

MySQL left join、right join和join的区别

androidstudio gradle下载速度慢

paddlex 使用-5 Andrdroid4.1报错插件无法删除

uoj316【NOI2017】泳池

NOIP2010提高组 机器翻译

标签