K Seq HihoCoder - 1046 || BZOJ4504 k个串

这题与超级钢琴类似，然而重复的不重复计算贡献。。

那么先求出数组nxt，nxt[i]表示第i个元素之后的第一个与其相等的元素的下标，不存在则nxt[i]=0

考虑取的区间左端点为1时的情况。

将读入序列a中相等元素都只保留最先出现的，其余变为0，然后求前缀和，得到数组b。

此时可以知道，设f(l,r)为取下标在[l,r]区间内数时的答案，那么f(1,r)=b[r]。

考虑取的区间左端点为2时的情况。如何维护b数组，使得新的b数组也满足f(2,r)=b[r]？

手模样例区间左端点为1和2时符合要求的b。

样例：

7 5
3 -2 1 2 2 1 3

l=1:  3  1  2 4 4 4 4
l=2:  0  -2 -1 1 1 1 4

可以发现，做的操作相当于将b数组内下标在[1,nxt[1]-1]区间内的数减了（原来的）b[1]。

进一步推出，左端点为l时的b数组变到左端点l+1的b数组，就相当于将下标在[l,nxt[l]-1]区间内的数减了（原来的）b[l]。

（当然如果nxt[i]=0，那么就是将[l,n]内减b[l]）

因此，可以用可持久化线段树处理出左端点为每一个位置时的b数组。可持久化线段树如果要传标记的话常数会很大（复杂度应该是对的...大概吧?），所以可以标记永久化

（不知道为什么网上的标记永久化那么长？吓得我还以为自己写错了233333）

（我写标记永久化时候困难重重，最后发现标记含义的定义还是类比普通线段树最容易实现（就是除当前节点外，以当前节点为根的子树内所有点的对应值都应加上当前节点的加法tag），另外给标记和记录的值一个明确的定义对于写清楚代码非常重要）

这样子之后就可以用类似超级钢琴的做法去做了...才怪。难道你真的跟我一样想要去写可持久化的带区间修改的区间第k大这样子一看就不靠谱的东西？

可以发现每一次对给定某一个b数组的查询，每次的区间都是一样的，一定是第一次第1大，第二次第2大，...

当然就可以用超级钢琴的后一种做法去做了（优先队列维护一下哪个b数组，哪一段区间的最大值是多少，在哪里，当某一段区间最大值被取出后，把该区间除了最大值所在位置剩下的最多两段取最大值放回优先队列）。'

（似乎也可以考虑暴力将原来的最大值加一个-inf？这样子下一次查找找到的就是该区间的次大啦（我没试过））

错误记录：

1.不知道为什么想到去维护最小值了，怎么过的样例啊

2.82-83行i+1写成i

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<tr1/unordered_map>
  5 #define inf 0x3f3f3f3f3f3f3f3f
  6 #define mid ((l+r)>>1)
  7 using namespace std;
  8 using namespace tr1;
  9 typedef long long LL;
 10 typedef pair<LL,LL> P;
 11 LL lc[30000010],rc[30000100],addv[30000100],mem;
 12 //addv[i]表示i区间加法tag
 13 P maxn[30000100];//一对值：区间(只考虑自身及其下节点的标记)的最大值及下标
 14 LL L,R,x;
 15 LL root[100100],nxt[100100],a[100100],b[100100];
 16 tr1::unordered_map<LL,LL> ttt1;
 17 void build(LL l,LL r,LL &num)
 18 {
 19     num=++mem;
 20     if(l==r)    {maxn[num]=P(b[l],l);return;}
 21     build(l,mid,lc[num]);build(mid+1,r,rc[num]);
 22     maxn[num]=max(maxn[lc[num]],maxn[rc[num]]);
 23 }
 24 void addx(LL l,LL r,LL &num)
 25 {
 26     LL t=num;num=++mem;lc[num]=lc[t];rc[num]=rc[t];maxn[num]=maxn[t];addv[num]=addv[t];
 27     if(L<=l&&r<=R)
 28     {
 29         addv[num]+=x;maxn[num].first+=x;
 30         return;
 31     }
 32     if(L<=mid)    addx(l,mid,lc[num]);
 33     if(mid<R)    addx(mid+1,r,rc[num]);
 34     maxn[num]=max(maxn[lc[num]],maxn[rc[num]]);
 35     maxn[num].first+=addv[num];
 36 }
 37 P query(LL l,LL r,LL num)
 38 {
 39     if(L<=l&&r<=R)    return maxn[num];
 40     P ans=P(-inf,1);
 41     if(L<=mid)    ans=max(ans,query(l,mid,lc[num]));
 42     if(mid<R)    ans=max(ans,query(mid+1,r,rc[num]));
 43     ans.first+=addv[num];
 44     return ans;
 45 }
 46 struct Info
 47 {
 48     Info(LL a=0,LL b=0,LL c=0,LL d=0,LL e=0)
 49         :ans(a),l(b),r(c),st(d),pos(e)
 50     {}
 51     LL ans,l,r,st,pos;
 52     //root[st]中，[l,r]内最大值是ans，在pos位置
 53     friend bool operator<(const Info &a,const Info &b)
 54     {
 55         return a.ans<b.ans;
 56     }
 57 };
 58 LL n,k;
 59 priority_queue<Info> q;
 60 int main()
 61 {
 62     LL i;P t;Info t2;
 63     scanf("%lld%lld",&n,&k);
 64     for(i=1;i<=n;i++)    scanf("%lld",&a[i]);
 65     for(i=1;i<=n;i++)
 66     {
 67         b[i]=b[i-1];
 68         if(ttt1.count(a[i])==0)
 69             b[i]+=a[i];
 70         else
 71             nxt[ttt1[a[i]]]=i;
 72         ttt1[a[i]]=i;
 73     }
 74     build(1,n,root[0]);
 75     L=1,R=n,t=query(1,n,root[0]);
 76     q.push(Info(t.first,1,n,0,t.second));
 77     for(i=1;i<n;i++)
 78     {
 79         root[i]=root[i-1];
 80         L=i,R=i,x=-query(1,n,root[i]).first;
 81         L=i,R=nxt[i]?nxt[i]-1:n,addx(1,n,root[i]);
 82         L=i+1/**/,R=n,t=query(1,n,root[i]);
 83         q.push(Info(t.first,i+1,n,i,t.second));//
 84     }
 85     for(i=1;i<k;i++)
 86     {
 87         t2=q.top();q.pop();
 88         L=t2.l,R=t2.pos-1;
 89         if(L<=R)
 90         {
 91             t=query(1,n,root[t2.st]);
 92             q.push(Info(t.first,L,R,t2.st,t.second));
 93         }
 94         L=t2.pos+1,R=t2.r;
 95         if(L<=R)
 96         {
 97             t=query(1,n,root[t2.st]);
 98             q.push(Info(t.first,L,R,t2.st,t.second));
 99         }
100     }
101     t2=q.top();
102     printf("%lld",t2.ans);
103     return 0;
104 }