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 }