题目链接：https://codeforces.com/contest/1288/problem/E
题目大意：现有一个初始为1至n的序列，对这个序列进行m次操作，每次操作会给定一个数，表示把序列中的这个数挪到序列最前面的位置，原本在它之前的数字依次向后挪一个位置。要求输出每个数字最靠前的位置和最靠后的位置。
思路：
（1）先考虑简单的，如果某个数字被选中过，那么它最靠前的位置就是1，否则为它的初始位置。
（2）本题的重点在于求每个数字最靠后的位置。在一个数字被选中之前，如果他后面的数字被选中了，它的位置就会+1，由此，一个数字最靠后的位置有如下的情况（设操作序列为S，count表示统计数量，distinct表示只统计不重复的）：
1.对任意数字x，如果Si = x（1<=i<=m）并且对于任意1<=j<i有Sj != x，x可能的最靠后位置=count(distinct Sk)（1<=k<i, Sk>x）+ x
2.对任意数字x，如果对于任意1<=i<=m有Si != x，x可能的最靠后位置=count(distinct Sk)（1<=k<=m, Sk>x）+ x
3.对任意数字x，如果x = Si = Sj（1<=i<j<=m）并且对于任意i<k<j有Sk != x，x可能的最靠后位置=count(distinct Sk)（i<k<j）+ 1
4.对任意数字x，如果Si = x（1<=i<=m）并且对于任意i<j<=m有Sj != x，x可能的最靠后位置=count(distinct Sk)（i<k<=m）+ 1
（3）也就是说，本题的核心在于统计某一区间内不重复元素的个数，由于n和m的数据量是3e5级别的，所以肯定不能暴力统计。此处，可以采用树状数组解决这一问题。从左至右依次处理操作序列S，对于Si，将它上次出现的位置置0（减一），位置i置1（加一）。每处理一个操作之前，计算区间和并更新该操作指定的数字的最靠后位置。
1 #define _USE_MATH_DEFINES 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <string.h> 5 #include <string> 6 #include <math.h> 7 #include <ctype.h> 8 #include <vector> 9 #include <stack> 10 #include <map> 11 #include <set> 12 #include <algorithm> 13 #include <iostream> 14 #include <limits.h> 15 #include <iomanip> 16 #include <queue> 17 #include <functional> 18 #include<utility> 19 #define el ‘\n‘ 20 #define M 1000005 21 const long double C = 0.57721566490153286060651209; 22 const long long N = 1e9+7; 23 #define ll long long 24 #define ull unsigned long long 25 using namespace std; 26 27 int t[300005]; 28 29 void update(int p,int x,int n) 30 { 31 while (p <= n) { 32 t[p]+=x; 33 p += p & -p; 34 } 35 } 36 37 int query(int p) 38 { 39 int ans=0; 40 while (p) { 41 ans+=t[p]; 42 p -= p & -p; 43 } 44 return ans; 45 } 46 47 int mp[300005]; 48 int Mp[300005]; 49 int a[300005]; 50 int ap[300005]; 51 52 int main() 53 { 54 int n,m; 55 cin>>n>>m; 56 for(int i=1;i<=n;i++){ 57 mp[i]=i; 58 Mp[i]=i; 59 } 60 61 for(int i=1;i<=m;i++){ 62 cin>>a[i]; 63 mp[a[i]]=1; 64 if(!ap[a[i]]){ 65 update(a[i],1,n); 66 ap[a[i]]=1; 67 Mp[a[i]]+=query(n)-query(a[i]); 68 } 69 } 70 for(int i=1;i<=n;i++){ 71 if(!ap[i]){ 72 Mp[i]+=query(n)-query(i); 73 } 74 } 75 for(int i=1;i<=n;i++){ 76 t[i]=0; 77 ap[i]=0; 78 } 79 for(int i=1;i<=m;i++){ 80 Mp[a[i]]=max(Mp[a[i]],query(i)-query(ap[a[i]])+1); 81 if(ap[a[i]])update(ap[a[i]],-1,m); 82 ap[a[i]]=i; 83 update(i,1,m); 84 } 85 for(int i=1;i<=n;i++){ 86 cout<<mp[i]<<‘ ‘; 87 if(!ap[i])cout<<Mp[i]<<el; 88 else 89 cout<<max(Mp[i],query(m)-query(ap[i])+1)<<el; 90 } 91 return 0; 92 }
补题：Educational Codeforces Round 80 (Rated for Div. 2) E. Messenger Simulator