现有$n-1$种化学物质，他们全部溶于水。任取$n-1$种化学物质中的两种都可以在一定条件下发生化学反应（两种可以相同）。特别地，水和其他化学物质不会化学反应，但是我们为了统一考虑，我们认为水可以和任意一种化学物质$X$反应生成$X$。那么包含水我们一共有$n$种化学物质。

根据相关理论，由于产物不离开溶液反应体系，化学药品之间反应的产物与加入药品的顺序无关。另外，每种化学物质都有恰好一种对应的化学物质，它们两个反应生成水。

现在桌子上有一排药瓶，每一个药瓶中存放了一种化学物质，编号从左到右分别为$1,2,\cdots,m$。为了体现您的超强实验功底，您的第$i$次实验仅用编号在区间$[L_i,R_i]$中的药瓶。假设您能创造出任何可能的反应条件，请问第$i$次实验您总共能配出多少种不同的物质（包含一开始就有的物质）？

输入格式

第一行三个正整数$t,m,q$，分别表示第二行正整数个数、桌子上化学药品的数量、您做实验的次数；

第二行为用于描述这些化学药品性质的$t$个正整数；

接下来一行$m$个$[1,n]$内的正整数，第$i$个整数表示编号为$i$的药品是第几种化学物质；

接下来$q$行，每行两个正整数$L_i,R_i$，表示第$i$次实验中您能使用的药品编号区间。

输出格式

恰好$q$行，每行一个$[1,n]$内的正整数，表示第$i$次实验您在理论上能配出的不同的物质种类数。

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

4
2
1

辅助代码

推荐使用C++解决本题。

namespace LIB{
    const int N=30;
    int dim[N],dimcnt;
    template<class T>void dfs(int dep,T g,int x,int y,int z,int n){
        if(dep>dimcnt){
            g[x][y]=z;
            return;
        }
        int d=n/dim[dep];
        for(int i=0;i<n;i+=d){
            for(int j=0;j<n;j+=d){
                dfs(dep+1,g,x+i,y+j,z+(i+j)%n,d);
            }
        }
    }
    template<class T1,class T2>inline int put_reaction(int t,T1 a,T2 g){
        dimcnt=t;
        int n=1;
        for(int i=1;i<=t;i++){
            n*=dim[i]=a[i];
        }
        dfs(1,g,1,1,1,n);
        return n;
    }
}

将以上代码包含在您的源程序内之后，您可以调用这个时间复杂度为$\mathrm O(n^2)$的函数来处理输入数据的前两行：

int LIB::put_reaction(t,a,g);

• 第一个参数是输入第一行的整数$t$；
• 第二个参数是一个int数组，里面从下标$1$开始存放着输入数据第二行的$t$个数；
• 第三个参数是一个int二维数组，函数执行完成之后，第i种物质和第j种物质反应的产物的是第g[i][j]种物质；
• 该函数返回一个int，表示【题目描述】中的$n$。

程序能根据描述化学药品性质的$t$个正整数生成一个二维int数组g。根据【题目描述】，该数组满足：

• 第i种化学物质和第j种化学物质反应生成第g[i][j]种化学物质；
• 产物与加入顺序无关，故g[i][j]==g[j][i]且g[g[i][j]][k]==g[i][g[j][k]]成立；
• $n$种物质中恰有一种是水，保证其反应性质满足题目中的描述；
• 二维数组g的每一行、每一列都恰有一个是水。

参考用法：

#include <cstdio>
namespace LIB{ /* ... */ }
const int N=3010;
int a[N],b[N][N];
int main(){
    int t,m,q;
    scanf("%d%d%d",&t,&m,&q);
    for(int i=1;i<=t;i++){
        scanf("%d",a+i);
    }
    int n=LIB::put_reaction(t,a,b);
    /* ... */
    return 0;
}

限制与约定

对于所有数据：

• $n\leq3000,m,q\leq10^6$；
• $\forall i,1\leq L_i\leq R_i\leq m$；
• $\forall i,a_i\neq 1$。

时间限制：$\texttt{2s}$

空间限制：$\texttt{512MB}$

下载

样例数据下载