题意：https://codeforc.es/contest/1208/problem/E
现有n行w列的墙,每行有一排连续方块，一排方块可以左右连续滑动，且每个方块都有一个价值，第i 列的价值定义为这列的方块的价值和。求1到w列中每列的最大价值。注：如果一个位置没有方块，那么这个位置的价值为0
思路：
直接RMQ+差分数组即可。
1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0); 2 #include <cstdio>//sprintf islower isupper 3 #include <cstdlib>//malloc exit strcat itoa system("cls") 4 #include <iostream>//pair 5 #include <fstream>//freopen("C:\\Users\\13606\\Desktop\\草稿.txt","r",stdin); 6 #include <bitset> 7 //#include <map> 8 //#include<unordered_map> 9 #include <vector> 10 #include <stack> 11 #include <set> 12 #include <string.h>//strstr substr 13 #include <string> 14 #include <time.h>//srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9; 15 #include <cmath> 16 #include <deque> 17 #include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less 18 #include <vector>//emplace_back 19 //#include <math.h> 20 //#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor 21 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare) 22 using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation 23 //****************** 24 int abss(int a); 25 int lowbit(int n); 26 int Del_bit_1(int n); 27 int maxx(int a,int b); 28 int minn(int a,int b); 29 double fabss(double a); 30 void swapp(int &a,int &b); 31 clock_t __STRAT,__END; 32 double __TOTALTIME; 33 void _MS(){__STRAT=clock();} 34 void _ME(){__END=clock();__TOTALTIME=(double)(__END-__STRAT)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;} 35 //*********************** 36 #define rint register int 37 #define fo(a,b,c) for(rint a=b;a<=c;++a) 38 #define fr(a,b,c) for(rint a=b;a>=c;--a) 39 #define mem(a,b) memset(a,b,sizeof(a)) 40 #define pr printf 41 #define sc scanf 42 #define ls rt<<1 43 #define rs rt<<1|1 44 typedef long long ll; 45 const double E=2.718281828; 46 const double PI=acos(-1.0); 47 //const ll INF=(1LL<<60); 48 const int inf=(1<<30); 49 const double ESP=1e-9; 50 const int mod=(int)1e9+7; 51 const int N=(int)1e6+10; 52 53 int dp[N][35],arr[N]; 54 55 void rmq_init(int n) 56 { 57 for(int i=1;i<=n;i++) 58 dp[i][0]=arr[i]; 59 for(int j=1;(1<<j)<=n;j++) 60 for(int i=1;i+(1<<j)-1<=n;i++) 61 dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]); 62 } 63 int rmq(int l,int r) 64 { 65 int k=log2(r-l+1); 66 return max(dp[l][k],dp[r-(1<<k)+1][k]); 67 } 68 ll ans[N]; 69 ll DP[N]; 70 71 void solve(int len) 72 { 73 int n; 74 sc("%d",&n); 75 for(int i=1;i<=n;++i) 76 sc("%d",&arr[i]); 77 rmq_init(n); 78 int L,R; 79 int max_=max(0,rmq(1,n)); 80 if(len>=2*n+1) 81 DP[n+1]+=max_,DP[len+1-n]-=max_; 82 for(int i=1;i<=n;++i) 83 { 84 L=max(1,n-(len-i)); 85 R=min(n,i); 86 if(n-(len-i)<1||i>n) 87 ans[i]+=max(0,rmq(L,R)); 88 else 89 ans[i]+=rmq(L,R); 90 } 91 int LL=max(n+1,len-n+1); 92 for(int i=LL;i<=len;++i) 93 { 94 L=max(1,n-(len-i)); 95 R=min(n,i); 96 if(n-(len-i)<1||i>n) 97 ans[i]+=max(0,rmq(L,R)); 98 else 99 ans[i]+=rmq(L,R); 100 } 101 } 102 103 void PR(ll _[],int n) 104 { 105 for(int i=1;i<=n;++i) 106 pr("%lld ",_[i]); 107 pr("\n"); 108 } 109 int main() 110 { 111 int n,m; 112 sc("%d%d",&n,&m); 113 for(int i=1;i<=n;++i)solve(m);//,PR(DP,m); 114 for(int i=1;i<=m;++i) 115 { 116 DP[i]+=DP[i-1]; 117 pr("%lld ",ans[i]+DP[i]); 118 } 119 // PR(DP,m); 120 return 0; 121 } 122 123 /**************************************************************************************/ 124 125 int maxx(int a,int b) 126 { 127 return a>b?a:b; 128 } 129 130 void swapp(int &a,int &b) 131 { 132 a^=b^=a^=b; 133 } 134 135 int lowbit(int n) 136 { 137 return n&(-n); 138 } 139 140 int Del_bit_1(int n) 141 { 142 return n&(n-1); 143 } 144 145 int abss(int a) 146 { 147 return a>0?a:-a; 148 } 149 150 double fabss(double a) 151 { 152 return a>0?a:-a; 153 } 154 155 int minn(int a,int b) 156 { 157 return a<b?a:b; 158 }