Input file: standard inputOutput file: standard outputTime limit: 1 secondMemory limit: 256 megabytes给一个长度为 $n$ 的整数序列 $A_1,A_2,\dots,A_n$然后有 $q$ 次询问每次询问给出两个整数 $x,y$问有多少个整数对 $(i,j)$ 满足 $1 \le i j \le n,\ A_i x,\ A_j y$。Input第一行两个整数 $n,q\ (1 \le n,q \le 10^5)$分别表示序列长度和询问个数。第二行 $n$ 个整数 $A_1,A_2,\dots,A_n\ (1 \le A_i \le 10^9)$表示给定的序列。接下来 $q$ 行每行两个整数 $x,y\ (1 \le x,y \le 10^9)$表示一次询问。Output输出 $q$ 行每行一个整数表示满足 $1 \le i j \le n,\ A_i x,\ A_j y$ 的整数对 $(i,j)$ 的个数。Examplestandard inputstandard outputpre11 33 1 4 1 5 9 2 6 5 3 53 51 34 8/prepre420/preNote对于第一组询问4 个满足条件的整数对为 $(1,5),(1,9),(1,11),(10,11)$。对于第二组询问2 个满足条件的整数对为 $(2,10),(4,10)$。对于第三组询问没有满足条件的整数对。可直接复制纯文本样例输入11 3 3 1 4 1 5 9 2 6 5 3 5 3 5 1 3 4 8输出4 2 0暴力能对 但是一定会超时正确方法 应该用mapint,vectorint前件存题目给的数字后件存这个数字的位置然后进行每次询问首先两个特判1.如果这个询问在之前询问过就输出原来存的数据所以这里涉及到记忆化。2.如果询问的两数字相同 就把vector的大小当成这个数的个数n*(n-1)/2就ok。然后判断询问的数字 前面的数字出现的次数也就是map[].size())多还是后面的数字出现次数多 就挑次数少的遍历 下面对两种情况一一分析·如果询问的第一个数a)出现次数少遍历a 找第一个大于当前循环的数的下标 找到后-b.begin()相当于在b数组中这个数的下标 b.size()减去这个下标 就是后面符合条件的下标的个数了·如果询问的第二个数(b)出现次数少遍历b 与a同理 只不过这次找到的数量是不符合的那几个 刚好相反 所以要减去#includebits/stdc.h using namespace std; #define int long long signed main(){ int n,m; cinnm; vectorint a(n); mapint,vectorint mp; mappairint,int,int memry; for(int i0;in;i){ cina[i]; mp[a[i]].push_back(i); } for(int i0;im;i){ int x,y; cinxy; if(memry.count({x,y})){ coutmemry[{x,y}]endl; continue; } auto amp[x],bmp[y]; int ans0; if(a.size()0||b.size()0){ ans0; } else if(xy){ int c(int)a.size(); ansc*(c-1)/2; } else if(a.size()b.size()){ for(int tt:a){ int posupper_bound(b.begin(),b.end(),tt)-b.begin(); ans(int)b.size()-pos; } } else{ int t0; for(int tt:b){ int posupper_bound(a.begin(),a.end(),tt)-a.begin(); t(int)a.size()-pos; } ans(int)a.size()*(int)b.size()-t; } memry[{x,y}]ans; coutansendl; } } /* 11 3 3 1 4 1 5 9 2 6 5 3 5 3 5 1 3 4 8 */