#总结
这三题代码量都能控制在80行以内2333
题解应该到下一个屏幕了吧……
#题目描述
##Task 1 DIVIDE-AND-CONQUER
坐标轴上\(N\)个点，每个点的坐标为\(x_i\)，有两个属性\(g_i\),\(d_i\)
选定一个区间\([i,j]\)使得\(x_j-x_i\le \sum_{k=i}^j d_k\)
最大化 \(\sum_{k=i}^j g_k\)
##Task 2 LUXURY-BURROW
圈定一个子矩阵，面积最小为\(k\)，最大化子矩阵元素最小值
##Task 3 TRADING
平面上若干条斜率为1的线段，横坐标从\(L_i\)到$R_i\(，给你线段在\)x=L_i\(处\)y$$的值，求每个点最上方的线段
#做法
##Task 1
由暴力的公式可以知道：一个区间可以被选的充分条件是\(d_j-d_{i-1}\ge x_j-x_i\)，推得\(d_j-x_j\ge d_{i-1}-x_i\)
我们用线段树维护\(d_j-x_j=k\)的最大的\(j\)的值
然后对于每个\(i\in [1,n]\)，找到满足\(d_j-x_j\ge d_{i-1}-x_i\)的最小的\(j\)
总时间复杂度\(O(n \log n)\)
##Task 2
二分答案，通过\(O(MN)\)的最大子矩阵DP判定答案合法性
##Task 3
根据题目知道，线段的斜率都为1，那么延长线段，直线交\(y\)轴的纵坐标的值就能代替函数的值
用线段树维护这个值即可
P.S. ZKW线段树特别方便
#AC Code
##Task 1
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <utility>
using namespace std;
const int maxn=100005,maxm=131072;
long long x[maxn],g[maxn],d[maxn];
int pos[262150],ipos[262150];
pair<long long,int> segv[maxn];
int seg[262150];
long long val[maxn];
int n;
int qmax(int l,int r)
{
int ans=0;
l=l+maxm-1;r=r+maxm+1;
while (l^r^1)
{
if (~l&1) ans=max(ans,seg[l+1]);
if ( r&1) ans=max(ans,seg[r-1]);
l>>=1;r>>=1;
}
return ans;
}
int main()
{
#ifdef EVAL
freopen("divide.in","r",stdin);
freopen("divide.out","w",stdout);
#endif
int apos=0,aapos;
long long ans=0;
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%lld%lld%lld",&x[i],&g[i],&d[i]);
g[i]+=g[i-1];
d[i]+=d[i-1];
val[i]=d[i]-x[i];
segv[i]=make_pair(d[i]-x[i],i);
}
sort(&val[1],&val[n+1]);
sort(&segv[1],&segv[n+1]);
for (int i=1;i<=n;i++)
{
pos[segv[i].second]=i,seg[i+maxm]=segv[i].second;
}
for (int i=maxm;i>=1;i--)
seg[i]=max(seg[i*2],seg[i*2+1]);
for (int i=1;i<=n;i++)
{
aapos=lower_bound(&val[1],&val[n+1],d[i-1]-x[i])-&val[0];
apos=qmax(aapos,n);
ans=max(ans,g[apos]-g[i-1]);
}
printf("%lld\n",ans);
return 0;
}
##Task 2
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1005;
int Map[maxn][maxn],val[maxn][maxn],h[maxn][maxn],la[maxn][maxn],ra[maxn][maxn];
int sta[maxn],tp;
int m,n,k;
int i,j;
int vmax=0;
int dp()
{
int ans=0,lo,ro;
//--
memset(h,0,sizeof(h));
for (i=1;i<=n;i++)
{
lo=0;ro=m+1;
for (j=1;j<=m;j++)
{
if (!Map[i][j])
h[i][j]=la[i][j]=0,lo=j;
else
{
h[i][j]=(i==1)?1:h[i-1][j]+1;
la[i][j]=(i==1)?lo+1:max(la[i-1][j],lo+1);
}
}
for (j=m;j>=1;j--)
{
if (!Map[i][j])
ra[i][j]=n+1,ro=j;
else
{
ra[i][j]=(i==1)?(ro-1):min(ra[i-1][j],ro-1);
ans=max(ans,h[i][j]*(ra[i][j]-la[i][j]+1));
}
}
}
return ans;
}
void erfen()
{
int l=0,r=vmax+1,mid,ans,rans=0;
while (l<r-1)
{
mid=(l+r)/2;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
Map[i][j]=(val[i][j]>=mid);
if (dp()>=k)
l=mid;
else
r=mid-1;
}
for (mid=l+2;mid>=l;mid--)
{
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
Map[i][j]=(val[i][j]>=mid);
if ((ans=dp())>=k)
break;
}
printf("%d %d\n",mid,ans);
}
int main()
{
#ifdef EVAL
freopen("burrow.in","r",stdin);
freopen("burrow.out","w",stdout);
#endif
scanf("%d%d%d",&n,&m,&k);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
scanf("%d",&val[i][j]),vmax=max(vmax,val[i][j]);
erfen();
return 0;
}
##Task 3
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=300005,maxm=524288;
int n,m;
int seg[1048580];
void edit(int l,int r,int v)
{
l=l+maxm-1;r=r+maxm+1;
while (l^r^1)
{
if (~l&1) seg[l+1]=max(seg[l+1],v);
if ( r&1) seg[r-1]=max(seg[r-1],v);
l>>=1;r>>=1;
}
}
int query(int x)
{
int ans(0x80808080);
x=x+maxm;
while (x)
{
ans=max(ans,seg[x]);
x>>=1;
}
return ans;
}
int main()
{
int li,ri,xi;
#ifdef EVAL
freopen("trading.in","r",stdin);
freopen("trading.out","w",stdout);
#endif
memset(seg,0x80,sizeof(seg));
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&li,&ri,&xi);
edit(li,ri,xi-li);
}
for (int i=1;i<=n;i++)
{
xi=query(i);
printf("%d ",(xi==int(0x80808080))?0:xi+i);
}
printf("\n");
return 0;
}