cf1208E. Let Them Slide

題意：

都放在一個(gè)長(zhǎng)度為W的框里面。有n個(gè)序到，第i個(gè)序列的長(zhǎng)度是1。這些序到并排放在一起，每一個(gè)序列都放在一個(gè)長(zhǎng)度為w的框里

這些序列可以在框里面滑動(dòng)，但是不能劃出框。

對(duì)于每一個(gè)位置，你需要求出怎樣滑動(dòng)可以使得這一個(gè)位置上的數(shù)的和最大

序到總長(zhǎng)度不超過(guò)$10^6，?10^9\le ai\le 10^9$

題解：

我一開始想法，對(duì)于每個(gè)位置的數(shù)，考慮其會(huì)被哪些框內(nèi)的數(shù)所影響，比如第i個(gè)數(shù)，看框內(nèi)通過(guò)移動(dòng)哪個(gè)區(qū)間可以給第i個(gè)數(shù)做貢獻(xiàn)，然后利用線段樹查詢區(qū)間最大值，代碼如圖

但是這樣對(duì)于每一位考慮，對(duì)于每一位查詢區(qū)間必T，因?yàn)閺?fù)雜度是$O(nwlogl)$
我們仔細(xì)觀察會(huì)發(fā)現(xiàn)，對(duì)于框內(nèi)元素i，對(duì)于大部分的$1<=j<=w$,數(shù)組i中的每個(gè)位置放在j列都是合法的，只有少部分是不合法的，也就是說(shuō)不合法的是少量，合法的大量，因此我們直接求合法會(huì)T，所有可以先將所有最大值累加，去除不可到達(dá)的區(qū)間的最大值。
由于數(shù)組長(zhǎng)度不超過(guò)1e6，特判不會(huì)超過(guò)2e6，因此最多進(jìn)行$2e6?log1e6$次操作，這樣就不會(huì)超時(shí)

區(qū)間len+1到w-len-1這一段就可以省掉計(jì)算，另外頭尾兩端計(jì)算更新答案。

代碼：

#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime = clock ();freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn=2e6+9; #define int long long int a[maxn]; int b[maxn]; struct tree{int l,r;int val;int lazy; }tr[maxn<<1]; void pushup(int rt){tr[rt].val=max(tr[rt<<1].val,tr[rt<<1|1].val); } void pushdown(int rt){if(tr[rt].lazy){tr[rt<<1].val+=tr[rt].lazy;tr[rt<<1].lazy+=tr[rt].lazy;tr[rt<<1|1].lazy+=tr[rt].lazy;tr[rt<<1|1].val+=tr[rt].lazy;tr[rt].lazy=0;} } void build(int rt,int l,int r){tr[rt].l=l;tr[rt].r=r;if(l==r){tr[rt].val=a[l];return ;}int mid=l+r>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);pushup(rt); } void update(int rt,int l,int r,int val) {if(tr[rt].l>r||tr[rt].r<l)return ;if(tr[rt].l>=l&&tr[rt].r<=r){tr[rt].lazy+=val;tr[rt].val+=val; return ;}pushdown(rt);update(rt<<1,l,r,val);update(rt<<1|1,l,r,val);pushup(rt); } int query(int rt,int l,int r){if(tr[rt].l>r||tr[rt].r<l)return -1e9-2;if(tr[rt].l>=l&&tr[rt].r<=r){return tr[rt].val;}pushdown(rt);return max(query(rt<<1,l,r),query(rt<<1|1,l,r)); } signed main() {rd_test();int n,w;cin>>n>>w;int sum=0;for(int i=1;i<=n;i++){int len;read(len);int mx=0;for(int j=1;j<=len;j++){read(a[j]);mx=max(mx,a[j]);}sum+=mx;build(1,1,len);for(int j=1;j<=min(w-len+1,len);j++){int cur=-1e9-9;int L=j+len-w,R=j;if(L<1) cur=0,L=1;if(R>len) cur=0,R=len;cur=max(cur,query(1,L,R));b[j]+=(cur-mx);}for(int j=w;j>=max(w-(len+1),w-len+2);j--){int cur=-1e9-9;int L=j-w+len,R=j;if(L<1) cur=0,L=1;if(R>len) cur=0,R=len;cur=max(cur,query(1,L,R));b[j]+=(cur-mx);} // update(1,1,n,0);}for(int i=1;i<=w;i++){cout<<sum+b[i]<<" ";}cout<<endl;return 0;//Time_test(); }

總結(jié)

以上是生活随笔為你收集整理的cf1208E. Let Them Slide的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。