RMQ+差分处理（Let Them Slide）Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)

题意：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("
");
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 }