原题大意

给一个长度为n的序列，和q个询问，每个询问有两个数x，y。问在所有的子序列中x，y出现次数相同的序列个数有多少？

算法分析

首先观察数据范围可以得出一下结论：

n的长度最多有8000，可以用离散化缩小单个数据范围
询问最多有500000，如果n小一点的话，肯定会有重复询问，可以有数组记录询问结果

然后考虑具体的询问

如果两个数相同或者都不在序列中，那么答案是n*(n+1)/2
如果只有一个数 x存在于序列 a, b, c, x, e, f, x, g, h, i, x中，我们可以将序列分割成如下形式[a,b,c],[e,f],[g,h,i]，然后按上一种情况处理每个区间。
如果两个数都存在于序列中，设前i个数里含x的有c个，含y的有d个，在前j（j < i）处，含x的有a个，含y的有b个，若使得（i，j]可以被选中，那么c-a == d-b，变型一下就是c-d == a-b。那么现在维护前缀就好了。因为序列中存在大量的非x，y的数，我们可以用vector记录x,y出现的位置，然后vector里的后一个减去前一个，就得到了中间的值，并加入到f[c-d]里去。最后结果就是遍历f,对于每一个f的值x，进行x*(x-1)/2,然后求和。

程序代码

#include <bits/stdc++.h>
typedef long long ll;
#define fi first
#define se second
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
const int maxn = 8005;
int n, q;
map<int, int> dict;
vector<int> adj[maxn];
int dp[maxn][maxn];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    int tot = 0;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        if(!dict.count(x)) dict[x] = ++tot;
        adj[dict[x]].pb(i);
    }
    mem(dp,-1);
    while(q--){
        int x, y;
        cin >> x >> y;
        x = dict[x];
        y = dict[y];

        if(dp[x][y] != -1){
            cout << dp[x][y] << "\n";
            continue;            
        }

        if(x == y)
        {
            dp[x][y] = n * (n+1) / 2;
            cout << dp[x][y] << "\n";
            continue;
        }

        map<int, int> mp;
        vector<pair<int, int> > v;
        int i = 0, j = 0;
        while((i < adj[x].size()) && (j < adj[y].size())){
            if(adj[x][i] < adj[y][j]){
                v.pb({adj[x][i], 0});
                i++;
            }
            else{
                v.pb({adj[y][j], 1});
                j++;
            }
        }
        while(i < adj[x].size()){
            v.pb({adj[x][i], 0});
            i++;
        }
        while(j < adj[y].size()){
            v.pb({adj[y][j], 1});
            j++;
        }
        int len = v.size();
        mp[0] = 1;
        if(len >= 1){
            mp[0]+=v[0].fi-1;
        }
        int cnt1 = 0, cnt2 = 0;
        for(i = 0; i < len - 1; i++){
            if(v[i].se == 0){
                cnt1++;
            }
            else cnt2++;
            mp[cnt1-cnt2] += v[i+1].fi - v[i].fi;
        }
        if(len >= 1 && i >= 0 && i < n){
            if(v[i].se == 0) cnt1++;
            else cnt2++;
            mp[cnt1-cnt2] += n+1 -v[i].fi;
        }
        ll ans = 0;
        for(auto p : mp){
            ll temp = p.se;
            ans += temp*(temp-1)/2;
        }
        dp[x][y] = ans;
        cout << dp[x][y] << "\n";
    }
    return 0;
}