找规律发现只要找到两个相同数字之间，有多少个不同的数字，即为答案。
可以用树状数组离线处理。
坑点是卡有很多张，没用完的情况，后面的卡直接放在哪里，
就是
10 5
1 2 3 4 5 这样
开始数据要输出到10
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> const int maxn = 1e5 + 20; int n,m; int c[maxn];//树状数组，多case的记得要清空 int lowbit (int x)//得到x二进制末尾0的个数的2次方 2^num { return x&(-x); } void add (int pos,int val)//在第pos位加上val这个值 { while (pos<=m) { //n是元素的个数 c[pos] += val; pos += lowbit(pos); } return ; } int get_sum (int pos) //求解：1--pos的总和 { int ans = 0; while (pos) { ans += c[pos]; pos -= lowbit(pos); } return ans; } int ans[maxn]; int a[maxn]; struct node { int L,R,id; bool operator < (const node &rhs) const { return R < rhs.R; } }query[maxn]; int ansQ[maxn]; int book[maxn]; int cur[maxn]; vector<int>pos[maxn]; void work () { int lenans = 0; scanf ("%d%d", &n, &m); for (int i = 1; i <= m; ++i) scanf ("%d", &a[i]); for (int i = 1; i <= n; ++i) cur[i] = 1; for (int i = 1; i <= m; ++i) { if (book[a[i]] == 0) { ans[++lenans] = a[i]; book[a[i]] = 1; } pos[a[i]].push_back(i); } for (int i = 1; i <= n; ++i) { if (book[i] == 0) { ans[++lenans] = i; } } memset (book, 0, sizeof book); for (int i = 1; i <= m; ++i) { if (pos[a[i]].size() <= cur[a[i]]) { query[i].L = i; query[i].R = m; query[i].id = i; } else { query[i].L = i; query[i].R = pos[a[i]][cur[a[i]]]; query[i].id = i; } cur[a[i]]++; } sort (query + 1, query + 1 + m); int now = 1; for (int i = 1; i <= m; ++i) { for (int j = now; j <= query[i].R; ++j) { if (book[a[j]]) { add(book[a[j]], -1); } book[a[j]] = j; add(j,1); } now = query[i].R + 1; ansQ[query[i].id] = get_sum(query[i].R) - get_sum(query[i].L - 1) - 1; } for (int i = 1; i <= lenans; ++i) { printf ("%d ",ans[i]); } printf (" "); for (int i = 1; i <= m; ++i) { printf ("%d ",ansQ[i]); } return ; } int main() { #ifdef local freopen("data.txt","r",stdin); #endif work (); return 0; }