找规律发现只要找到两个相同数字之间，有多少个不同的数字，即为答案。
可以用树状数组离线处理。
坑点是卡有很多张，没用完的情况，后面的卡直接放在哪里，
就是
10 5
1 2 3 4 5 这样
开始数据要输出到10
#include#include #include #include #include using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include #include #include 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 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 ("\n"); for (int i = 1; i <= m; ++i) { printf ("%d\n",ansQ[i]); } return ;}int main(){#ifdef local freopen("data.txt","r",stdin);#endif work (); return 0;}