牛客2018暑期多校第一场

Vexoben

Jul 24, 2018

It takes 37 minutes to read this article.

牛客多校第一场的题解……补了三天才大概补得差不多了……感觉还是菜得不行啊

（刷新以获取数学公式）

A.Monotonic Matrix

题意

给定一个 $n*m$ 的网格，在每个格子中填入 $0,1,2$ 中的一个数。要求每行，每列填的数字非严格递增。输出方案数膜1e9+7。

多组数据，n,m<=1000， $n$ 总和不超过100000

题解

很容易想到这就是两条分界线，一条是0与1的分界，一条是1和2的分界，都是从 $(0,n+1)$ 到 $(m+1,0)$ ，且前者不会跑到后者的下面。

直接DP的话复杂度是O(n^5)。

正解是运用Lindström–Gessel–Viennot lemma定理。

假设平面上有 $2n$ 个不同的点，从其中的 $n$ 个点出发走到另外 $n$ 个点，令 $M$ 等于：

其中 $e(a_i,b_j)$ 是从 $a_i$ 走到 $b_j$ 的方案数，则路径不相交的方案数就是 $det(M)$

所以我们把原来的模型转化一下，变成一条从 $(0,n+1)$ 走到 $(m+1,0)$ ，另一条从 $(1,n+2)$ 走到 $(m+2,1)$ ，两条不能相交的方案数。显然这就等于 $C(n+m,m)*C(n+m,m)-C(n+m,m-1)*C(n+m,n-1)$

比赛的时候怎么推呢？果断oeis。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2005;
const int mod=1e9+7;

LL C[N][N];

int main() {
	C[0][0]=1;
	for (int i=1;i<N;i++) {
		C[i][0]=1;
		for (int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	}
	int n,m;
	while (~scanf("%d%d",&n,&m)) {
		LL ans=C[m+n][n]*C[m+n][n]-C[m+n][m-1]*C[m+n][n-1];
		ans%=mod; if (ans<0) ans+=mod;
		printf("%lld\n",ans);
	}
	return 0;
}

B.Symmetric Matrix

题意

求满足下述条件的 $n*n$ 的矩阵 $A$ 的个数，满足：

1、 $A_{i,j}=0，1，2$

2、 $A_{i,i}=0$ ；

3、每行和为2；

4、 $A=A^T$

多组数据，n<=100000， $n$ 总和不超过 $1e7$ ,答案膜m(m<=1e9)输出

题解

首先要发现这描述的是一张无自环且每个点度数均为2的无向图的邻接矩阵。

于是问题转化为图的计数问题。

记 $dp[n]$ 为 $n$ 个点时的答案

下面考虑转移。有两种情况：

1、节点 $n$ 和前面某个点连了两条边，有 $(n-1)*dp[n-2]$ 种情况。

2、节点 $n$ 和前面一些点形成了环。注意这是可以翻转的环排列，所以它的方案数是：

$\sum_{i=2}^{n-1}\dbinom{n-1}{i}*dp[n-i-1]*\frac{(i+1)!}{2(i+1)}$

因此有：

$dp[n]=(n-1)*dp[n-2]+\sum_{i=2}^{n-1}\dbinom{n-1}{i}*dp[n-i-1]*\frac{(i+1)!}{2(i+1)}$

拆掉组合数，

$dp[n]=(n-1)*dp[n-2]+\frac{(n-1)!}{2}*\sum_{i=2}^{n-1}\frac{dp[n-i-1]}{(n-i-1)!}$

整理一下，

$dp[n]=(n-1)*dp[n-2]+\frac{(n-1)!}{2}*\sum_{i=1}^{n-3}\frac{dp[i]}{i!}$

令 $dp[n]=(n-1)*dp[n-2]+g[n]$ ，则

$g[n]=\frac{(n-1)!}{2}*\sum_{i=1}^{n-3}\frac{dp[i]}{i!}$

联立:

$\frac{2*g[n]}{(n-2)!}=\sum_{i=1}^{n-3}\frac{dp[i]}{i!}$ $\frac{2*g[n-1]}{(n-3)!}=\sum_{i=1}^{n-4}\frac{dp[i]}{i!}$

相减并化简：

$g[n]=(n-1)*g[n-1]+\frac{(n-1)(n-2)}{2}*dp[n-3]$

然后就可以 $O(n)$ 递推了。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+10;

int n,mod;
LL f[N],g[N];

void Solve() {
	f[0]=f[2]=1%mod;
	for (int i=3;i<=n;i++) {
		g[i]=1LL*(i-1)*g[i-1]%mod+1LL*(i-1)*(i-2)/2%mod*f[i-3]%mod;
		while (g[i]>=mod) g[i]-=mod;
		f[i]=(1LL*(i-1)*f[i-2]+g[i])%mod;
	}
	printf("%lld\n",f[n]);
}

int main() {
	while (~scanf("%d%d",&n,&mod)) Solve();
}

C.Fluorescent 2

题意

有 $n$ 个开关和 $m$ 盏灯，一开始所有灯亮着。再给定01矩阵 $C$ ，若 $C_{i,j}=1$ ，则按下开关 $i$ ，第 $j$ 盏灯的亮灭会改变。设按下开关的集合为 $S$ ，令 $f(S)$ 为按下S后亮的灯的盏数，求出所有 $2^n$ 种按开关方案的 $f(S)$ 的立方和。

n<=50,m<=1000

题解

并没有听懂叉姐说了什么，不知道自己的理解有没有问题……

首先我们将计数问题转化为概率期望问题。

用 $X_i$ 表示第 $i$ 盏灯是否亮着， $E((\sum_{i=1}^{m}))^3$ 为选一次的期望答案，那么最终答案就是 $E*2^n$

考虑计算这个期望，我们有：

$E((\sum_{i=1}^{m}X_i))^3 =\sum_{i,j,k=1}^{m}pr[X_i X_j X_k]$

所以只需要枚举 $i,j,k$ ，计算它们都亮的概率即可。

不妨考虑只有 $i,j,k$ 这三列的矩阵 $A$ 。

有一个结论是 $pr[x_i X_j X_k]=\frac{1}{2^{rank(A)}}$

注意矩阵的秩=行秩=列秩

可以这样理解那个结论：

以 $rank(A)=2$ 为例，假设我们选出了两个线性无关的行向量 $\alpha_1$ ， $\alpha_2$ ，模2意义下，其他所有向量都可以被 $\alpha_1$ ， $\alpha_2$ 线性表出。当我们随意选择其他向量的时候，异或运算相当于模2意义下的加法，所得结果仍旧能被 $\alpha_1$ ， $\alpha_2$ 线性表出。同时表出方法又是唯一的。所以在 $\alpha_1$ ， $\alpha_2$ 的4种系数搭配中，有且仅有一种可以使 $i,j,k$ 三盏灯同时为亮。

这样的话只需要枚举一列，将其他列做高消就可以统计出秩为 $0,1,2,3$ 的选择方案了。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1005;
const int mod=1e9+7;

int n,m;
LL f[N],g[N],ans[4];

void Gauss(LL x) {
	LL bit=0;
	for (int i=0;i<=51;i++) {
		if (x&(1LL<<i)) bit=(1LL<<i);
	}
	for (int i=1;i<=m;i++) {
		if (g[i]&bit) g[i]^=x;
	}
}

LL Qpow(LL x,LL p) {
	LL ans=1;
	while (p) {
		if (p&1) ans=ans*x%mod;
		x=x*x%mod; p>>=1;
	}
	return ans;
}

int main() {
	while (scanf("%d%d",&n,&m)==2) {
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		memset(ans,0,sizeof(ans));
		for (int i=1;i<=n;i++) {
			char s[1005];
			scanf("%s",s+1);
			for (int j=1;j<=m;j++) {
				f[j]|=(1LL<<(i-1))*(s[j]=='1');
			}
		}
		for (int i=1;i<=m;i++) {
			for (int j=1;j<=m;j++) g[j]=f[j];
			Gauss(f[i]);
			sort(g+1,g+m+1); g[m+1]=-1;
			LL las=1,sum=0,sum2=0;
			if (f[i]==0) {
				for (int j=1;j<=m+1;j++) {
					if (g[j]!=g[las]) {
						if (g[las]==0) sum=(sum+j-las)%mod,ans[0]+=sum*sum%mod;
						else {
							LL del=j-las;
							ans[1]+=del*del%mod;
							ans[1]+=del*sum*2%mod;
							ans[2]+=del*sum2*2%mod;
							sum2=(sum2+del)%mod;
						}
						las=j;
					}
				}
			}
			else {
				for (int j=1;j<=m+1;j++) {
					if (g[j]!=g[las]) {
						if (g[las]==0) sum=(sum+j-las)%mod,ans[1]+=sum*sum%mod;
						else {
							LL del=j-las;
							ans[2]+=del*del%mod;
							ans[2]+=del*sum*2%mod;
							ans[3]+=del*sum2*2%mod;
							sum2=(sum2+del)%mod;
						}
						las=j;
					}
				}
			}
		}
		LL res=0;
		for (int i=0;i<=3;i++) res+=Qpow(2,mod+n-i-1)*ans[i]%mod;
		printf("%lld\n",res%mod);
	}
	return 0;
}

D.Two Graphs

水题略过

图不同取决于边不同所以要hash，一开始贡献了一发罚时。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=8;
const int mod1=1e9+7;
const int mod2=1e9+9;
 
int ans;
int n,m1,m2,a[N][N],b[N][N];
int to[N],use[N*N];
map<LL,int> Map;
 
void check() {
    memset(use,0,sizeof(use));
    int flag=1;
    for (int i=0;i<n;i++) {
        for (int j=i+1;j<n;j++) {
            if (a[i][j]) {
                if (b[to[i]][to[j]]==0) flag=0;
                int a=to[i],b=to[j];
                if (a>b) swap(a,b);
                a=a*n+b;
                use[a]=1;
            }
        }
    }
    if (!flag) return;
    int ha1=0,ha2=0;
    for (int i=0;i<n*n;i++) {
        ha1=(97LL*ha1+use[i])%mod1;
        ha2=(97LL*ha2+use[i])%mod2;
    }
    LL ha=1LL*ha1*mod2+ha2;
    if (Map[ha]) return;
    Map[ha]=1;
    ans+=flag;
}
 
void dfs(int x) {
    if (x==n) check();
    for (int i=0;i<n;i++) {
        if (~to[i]) continue;
        to[i]=x;
        dfs(x+1);
        to[i]=-1;
    }
}
 
void Solve() {
    ans=0; Map.clear();
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(to,0xff,sizeof(to));
    for (int i=1;i<=m1;i++) {
        int x,y; scanf("%d%d",&x,&y);
        a[x-1][y-1]=a[y-1][x-1]=1;
    }
    for (int i=1;i<=m2;i++) {
        int x,y; scanf("%d%d",&x,&y);
        b[x-1][y-1]=b[y-1][x-1]=1;
    }
    dfs(0);
    cout<<ans<<endl;
}
 
int main() {
    while (~scanf("%d%d%d",&n,&m1,&m2)) Solve();
    return 0;
}

E.Removal

题意

给定字符集大小不超过10的字符串 $S$ ，去掉 $m$ 个字符，问可以得到多少不同的串。

n<=100000,m<=10

题解

显然是DP。难点在于排除重复。

令 $dp[i][j]$ 表示前 $i$ 个字符，删了 $j$ 个的方案数。

考虑重复计数是怎么来的。如果令 $dp[i][j]=dp[i-1][j]+dp[i-1][j-1]$ ，当遇到字符串 $xsx$ 时候，删除 $xs$ 和删除 $sx$ 就会被记为两种。

那么令 $pre[c]$ 表示字符 $c$ 上一次出现的位置，转移方程改为 $dp[i][j]=dp[i][j-1]+dp[i][j]-dp[pre[s[i]]][j-i+pre[s[i]]]$ 即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int mod=1e9+7;

int n,m,k,a[N],pre[12],f[N][11];

inline void Add(int &x,int y) {
	x+=y; if (x>=mod) x-=mod;
}

inline void Sub(int &x,int y) {
	x-=y; if (x<0) x+=mod;
}

int main() {
	while (~scanf("%d%d%d",&n,&m,&k)){
		memset(pre,0,sizeof(pre));
		memset(f,0,sizeof(f));
		for (int i=1;i<=n;i++) scanf("%d",&a[i]);
		f[0][0]=1;
		for (int i=1;i<=n;i++) {
			f[i][0]=1;
			int d=pre[a[i]]; pre[a[i]]=i;
			for (int j=1;j<=m;j++) {
				Add(f[i][j],f[i-1][j]);
				Add(f[i][j],f[i-1][j-1]);
				if (d&&(j-i+d)>=0) Sub(f[i][j],f[d-1][j-i+d]);
			}
		}
		printf("%d\n",f[n][m]);
	}
	return 0;
}

F.Sum of Maximum

题意

给定数组 $a$ ，计算:

$\sum_{x_1=1}^{a_1} \sum_{x_2=1}^{a_2}... \sum_{x_n=1}^{a_n} max(x_1,x_2,...,x_n)$

n<=100000,ai<=1e9

题解

不妨设a1<=a2<=…<=an

枚举最大值，考虑最大值在 $a_p+1$ 到 $a_{p+1}$ 直接的答案为：

$S$ 为 $a_1$ 到 $a_p$ 的乘积。最大值为 $i$ 的方案数就是后面 $n-p$ 个数在 $1$ 到 $i$ 乱选减去在 $1$ 到 $i-1$ 乱选的方案数。

将这个式子展开裂项得到：

$S*(a_{p+1}^{n-p+1}-(a_{p}+1)*a_{p}^{n-p}+\sum_{i=a_p+2}^{a_{p+1}-1}i^{n-p})$

求和那段拉格朗日插值一下即可。

因为不会拉格朗日插值就拿了队友的代码233

#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int MAXN=1005;
const LL Md=1000000007;
LL a[MAXN], p[MAXN][MAXN], fac[100111], g[MAXN][MAXN], k, mns, pls;
int n;
 
inline int Powe(LL x, LL y) {
    LL res=1;
    while(y) {
        if(y&1) res=res*x%Md;
        x=x*x%Md;
        y>>=1;
    }
    return res;
}
 
inline void prepare() {
    fac[0]=fac[1]=1;
    for(LL i=2;i<=100005;++i) {
        fac[i]=fac[i-1]*i%Md;
    }
}
 
inline LL Lagrange(LL n, LL k) {
    if(n<=0) return 0ll;
    if(n<=k+2) return p[k][n];
    n%=Md;
    LL gg=n-1;
    for(LL i=2;i<=k+2;++i) {
        gg=gg*(n-i)%Md;
    }
    LL ans=0;
    for(register int i=1;i<=k+2;++i) {
        LL ss=gg*Powe(n-i, Md-2)%Md;
        LL tt=fac[i-1]*fac[k+2-i]*((k+2-i)&1 ? -1ll : 1ll)%Md;
        ans+=p[k][i]*ss%Md*g[k][i]%Md;
        if(ans>=Md) ans-=Md;
        if(ans<0) ans+=Md;
    }
    return (ans+Md)%Md;
}
 
int main() {
    prepare();
    for(int i=1;i<=1002;++i) {
        p[i][0]=0;
        for(LL j=1;j<=i+2;++j) {
            g[i][j]=Powe(fac[j-1]*fac[i+2-j]*((i+2-j)&1 ? -1ll : 1ll)%Md, Md-2);
            p[i][j]=p[i][j-1]+Powe(j, i);
            if(p[i][j]>=Md) p[i][j]-=Md;
        }
    }
    while(scanf("%d", &n)==1) {
        for(int i=1;i<=n;++i) {
            scanf("%lld", &a[i]);
        }
        sort(a+1, a+1+n);
        LL sum=1, ans=0;
        for(int i=1;i<=n;++i) {
            if(a[i]==a[i-1]) {
                sum=sum*a[i]%Md;
                continue;
            }
            LL x=a[i-1]+1, y=a[i], m=n-i+1;
            ans+=sum*(Powe(y, m+1)-x*Powe(x-1, m)%Md-(Lagrange(y-1, m)-Lagrange(x-1, m)))%Md;
            if(ans>=Md) ans-=Md;
            if(ans<0) ans+=Md;
            sum=sum*a[i]%Md;
        }
        printf("%lld\n", (ans%Md+Md)%Md);
    }
    return 0;
}

H.Longest Path

题意

给定一棵树，边有边权。两点间的距离定义为相邻边权平方差的和。对于每个点，求出树上最远距离。

n<=100000,c<=100000

题解

令 $dn[x]$ 表示从 $x$ 的父亲向下走，经过 $x$ 向下走的最远距离。

再考虑一个点向上走的情况。一个点要么沿着父亲向上走的路走，要么走到自己的一个兄弟节点。

第一种情况很好处理。考虑第二种。

设 $fc[x]$ 为点 $x$ 与其父亲相连边的颜色。

那么它往兄弟节点走的最大权值就是：

$max((fc[x]-fc[y])^2+dn[y])$

对所有父亲相同的点按fc排序，然后斜率优化O(n)求解即可。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e5+10;

int n,m,E=0;
int fa[N],fir[N],nex[N<<1],arr[N<<1],q[N<<2];
LL up[N],dn[N],fc[N],val[N];
vector<int> p;

inline void Add_Edge(int x,int y,LL c) {
	nex[++E]=fir[x];
	fir[x]=E; arr[E]=y; val[E]=c;
}

void dfs(int x) {
	for (int i=fir[x];i;i=nex[i]) {
		if (arr[i]==fa[x]) continue;
		fc[arr[i]]=val[i];
		fa[arr[i]]=x;
		dfs(arr[i]);
		LL dx=dn[arr[i]];
		if (fc[x]) dx+=(fc[x]-fc[arr[i]])*(fc[x]-fc[arr[i]]);
		dn[x]=max(dn[x],dx);
	}
}

inline LL sqr(const LL &x)  { return x*x; }
inline LL x(int &u) { return fc[u]; }
inline LL dx(int &u, int &v) { return x(u)-x(v); }
inline LL y(int &u) { return dn[u]+sqr(fc[u]); }
inline LL dy(int &u, int &v) { return y(u)-y(v); }

void Updata() {
	int top=0;
	for (int i=0;i<p.size();i++) {
		int u=p[i];
		while (top>1&&dy(q[top],q[top-1])<2*fc[u]*dx(q[top],q[top-1])) top--;
		int v=q[top];
		if (v) up[u]=max(up[u],dn[v]+sqr(fc[u]-fc[v]));
		while (top>1&&dy(q[top],q[top-1])*dx(u,q[top])<dy(u,q[top])*dx(q[top],q[top-1])) top--;
		q[++top]=u;
	}
	top=0;
	for (int i=p.size()-1;i>=0;i--) {
		int u=p[i];
		while (top>1&&dy(q[top],q[top-1])<2*fc[u]*dx(q[top],q[top-1])) top--;
		int v=q[top];
		if (v) up[u]=max(up[u],dn[v]+sqr(fc[u]-fc[v]));
		while (top>1&&dy(q[top],q[top-1])*dx(u,q[top])>dy(u,q[top])*dx(q[top],q[top-1])) top--;
		q[++top]=u;
	}
}

bool cmp(int x,int y) {
	return (fc[x]<fc[y]);
}

void dfs2(int x) {
	p.clear();
	for (int i=fir[x];i;i=nex[i]) {
		if (arr[i]==fa[x]) continue;
		LL dx=up[x];
		if (fc[x]) dx+=(fc[x]-fc[arr[i]])*(fc[x]-fc[arr[i]]);
		up[arr[i]]=dx;
		p.push_back(arr[i]);
	}
	sort(p.begin(),p.end(),cmp);
	Updata();
	for (int i=fir[x];i;i=nex[i]) {
		if (arr[i]==fa[x]) continue;
		up[x]=max(up[x],dn[arr[i]]);
		dfs2(arr[i]);
	}
}

int main() {
	while (cin>>n) {
		E=0;
		memset(dn,0,sizeof(dn));
		memset(fa,0,sizeof(fa));
		memset(up,0,sizeof(up));
		memset(fir,0,sizeof(fir));
		for (int i=1;i<n;i++) {
			int x,y,c; scanf("%d%d%d",&x,&y,&c);
			Add_Edge(x,y,c); Add_Edge(y,x,c);
		}
		dfs(1); dfs2(1);
		for (int i=1;i<=n;i++) printf("%lld\n",up[i]);
	}
	return 0;
}

I.Substrings

题意

对于两个字符串 $S$ , $T$ ，若存在一个字符集的排列 $P$ ，使得将 $S[i]$ 替换为 $P[S[i]]$ 后和 $T$ 相等，则称 $S$ 和 $T$ 同构。

给定字符串 $S$ ，试求最大的子串集合大小，使集合中串互不同构。

n<=100000，字符集={‘a’,’b’,’c’}

题解

枚举6种同构方案，将6个串建出一个广义后缀自动机，统计本质不同子串个数 $x$ 。

只有一种字符的串会被计数3次，其余被计数6次。

设第一种串个数为 $y$ ，则答案为 $\frac{x+3y}{6}$

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e6+10;

namespace SAM {
	int tot=1,las=1,rt=1;
	int len[N],pre[N],ch[N][3];
	
	inline int Nw(int l) {
		len[++tot]=l;
		return tot;
	}

	inline void insert(int c) {
		int p=las,np=las=Nw(len[p]+1);
		while (!ch[p][c]) ch[p][c]=np,p=pre[p];
		if (!p) pre[np]=rt;
		else {
			int q=ch[p][c],nq;
			if (len[p]+1==len[q]) pre[np]=q;
			else {
				nq=Nw(len[p]+1);
				memcpy(ch[nq],ch[q],sizeof(ch[q]));
				pre[nq]=pre[q]; pre[q]=pre[np]=nq;
				while (ch[p][c]==q) ch[p][c]=nq,p=pre[p];
			}
		}
	}
}
using namespace SAM;

int n,cnt,a[N],to[3],use[N][3];
char s[N];

int main() {
	while (cin>>n) {
		tot=las=rt=1; cnt=0;
		memset(pre,0,sizeof(pre));
		memset(ch,0,sizeof(ch));
		memset(len,0,sizeof(len));
		memset(use,0,sizeof(use));
		scanf("%s",s+1);
		for (int i=1;i<=n;i++) a[i]=s[i]-'a';
		int now=-1,sx=0;
		for (int i=1;i<=n;i++) {
			if (now!=a[i]) now=a[i],sx=1;
			else sx++;
			cnt=max(cnt,sx);
		}
		for (to[0]=0;to[0]<3;to[0]++) {
			for (to[1]=0;to[1]<3;to[1]++) {
				for (to[2]=0;to[2]<3;to[2]++) {
					if (to[0]+to[1]+to[2]!=3) continue;
					if (to[0]*to[1]*to[2]!=0) continue;
					las=rt;
					for (int i=1;i<=n;i++) insert(to[a[i]]);
				}
			}
		}
		LL ans=cnt*3;
		for (int i=1;i<=tot;i++) ans+=len[i]-len[pre[i]];
		printf("%lld\n",ans/6);
	}
	return 0;
}

J.Different Integers

签到题，略。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int maxn=1e5+500;
int n,Q,sq;
int block[maxn],a[maxn],cnt[maxn],res[maxn];
int ans=0;
struct query {
    int l,r,idx;
    bool operator < (const query &rhs) const {
        return block[l]==block[rhs.l]?r<rhs.r:l<rhs.l;
    }
}q[maxn];
/*==================Define Area================*/
void Modify(int x,int d) {
    cnt[a[x]]+=d;
    if(d>0) ans+=cnt[a[x]]==1;
    else ans-=cnt[a[x]]==0;
}
 
int main() {
    while(scanf("%d%d",&n,&Q)!=EOF) {
        sq=sqrt(n);
        memset(cnt,0,sizeof cnt);
        ans=0;
        for(int i=1;i<=n;i++) {
            read(a[i]);
            block[i]=i/sq+1;
        }
        for(int i=1;i<=Q;i++) {
            read(q[i].l);read(q[i].r);
            q[i].idx=i;
        }
        sort(q+1,q+1+Q);
        int l=0,r=n+1;
        for(int i=1;i<=Q;i++) {
            while(l<q[i].l) Modify(l+1,1),l++;
            while(l>q[i].l) Modify(l,-1),l--;
            while(r<q[i].r) Modify(r,-1),r++;
            while(r>q[i].r) Modify(r-1,1),r--;
            res[q[i].idx]=ans;
        }
        for(int i=1;i<=Q;i++) {
            printf("%d\n",res[i]);
        }
    }
}

牛客2018暑期多校 第一场