主席树，先预处理出pre数组，pre[i]表示上一个ai出现的位置，然后假设区间从[1,R-1]变成了[1,R]，那么区间[pre[R]+1,R]内的数字需要加上ar，我们按照右端点从小到大建主席树，然后将每个版本的线段树中的最大的元素都丢进堆中，需要记录的是最大的元素对应的线段树版本以及其在线段树中的位置。那么求第k大只需要从堆中取出最大的元素，在其对应的线段树版本中去除掉这个元素，并且在这个版本的线段树中再取一个最大元素插入堆中，重复k-1次后堆顶元素即为答案。
代码
1 #include<cstdio> 2 #include<map> 3 #include<algorithm> 4 #include<set> 5 #include<queue> 6 #define fi first 7 #define sc second 8 #define mp make_pair 9 #define N 10000010 10 #define M 100010 11 using namespace std; 12 typedef long long ll; 13 int l[N],r[N],ls[N],rs[N]; 14 int a[M],id[M]; 15 ll v[N],inf; 16 struct g{ 17 ll v; 18 int pos; 19 }s[N]; 20 struct gg{ 21 ll a; 22 int b,c; 23 }q; 24 bool operator <(gg u,gg v){return u.a<v.a;} 25 priority_queue<gg> Q; 26 int tt,n,m,i,pre[N],root[N]; 27 map<int,int> ma; 28 void build(int &x,int a,int b) 29 { 30 x=++tt; 31 l[x]=a;r[x]=b;s[x].pos=b; 32 if (b-a>1) 33 { 34 int m=(a+b)>>1; 35 build(ls[x],a,m); 36 build(rs[x],m,b); 37 } 38 } 39 void insert(int &x,int y,int a,int b,ll c) 40 { 41 tt++;x=tt; 42 l[x]=l[y];r[x]=r[y]; 43 ls[x]=ls[y];rs[x]=rs[y]; 44 v[x]=v[y]; 45 s[x]=s[y]; 46 if ((a<=l[x])&&(r[x]<=b)) 47 { 48 v[x]+=c; 49 s[x].v+=c; 50 return; 51 } 52 int m=(l[x]+r[x])>>1; 53 if (a<m) insert(ls[x],ls[y],a,b,c); 54 if (m<b) insert(rs[x],rs[y],a,b,c); 55 if (s[ls[x]].v>s[rs[x]].v) 56 { 57 s[x].v=s[ls[x]].v+v[x]; 58 s[x].pos=s[ls[x]].pos; 59 } 60 else 61 { 62 s[x].v=s[rs[x]].v+v[x]; 63 s[x].pos=s[rs[x]].pos; 64 65 } 66 } 67 pair<ll,int> query(int x,int a,int b,ll c) 68 { 69 if ((a<=l[x])&&(r[x]<=b)) 70 return mp(s[x].v+c,s[x].pos); 71 int m=(l[x]+r[x])>>1; 72 pair<ll,int> tmp,ans; 73 ans.fi=-inf; 74 if (a<m) 75 { 76 tmp=query(ls[x],a,b,c+v[x]); 77 if (tmp.fi>ans.fi) ans=tmp; 78 } 79 if (m<b) 80 { 81 tmp=query(rs[x],a,b,c+v[x]); 82 if (tmp.fi>ans.fi) ans=tmp; 83 } 84 return ans; 85 } 86 int main() 87 { 88 inf=1000000000; 89 inf=inf*1000000; 90 scanf("%d%d",&n,&m); 91 for (i=1;i<=n;i++) 92 { 93 scanf("%d",&a[i]); 94 pre[i]=ma[a[i]]; 95 ma[a[i]]=i; 96 } 97 build(root[0],0,n); 98 for (i=1;i<=n;i++) 99 { 100 insert(root[i],root[i-1],pre[i],i,a[i]); 101 id[i]=i; 102 pair<ll,int> tmp=query(root[i],0,i,0); 103 q.a=tmp.fi;q.b=tmp.sc;q.c=i; 104 Q.push(q); 105 } 106 int cnt=n; 107 for (i=1;i<m;i++) 108 { 109 q=Q.top();Q.pop(); 110 insert(root[++cnt],root[id[q.c]],q.b-1,q.b,-inf); 111 id[q.c]=cnt; 112 pair<ll,int> tmp=query(root[cnt],0,q.c,0); 113 q.a=tmp.fi;q.b=tmp.sc; 114 Q.push(q); 115 } 116 printf("%lld ",Q.top().a); 117 } 118 /* 119 8 5 120 3 -2 1 2 2 1 3 -2 121 */