2019 杭电多校第六场的一道签到题
这次我们显然要求的二维矩阵的最大值, 分析题目我们可以得到几个细节.
1. 首先数据很大, 肯定要离散化.
2. 离散化后, 我们想象有很多点在一个平面内, 要统计矩阵最大值
3. 我们之前接触过如何求一条线上的最大子段和, 只要用线段树维护四个值就能够解决
4. 根据已知, 我们发现求矩阵和也是可以这么做的, 因为他是一个矩形, 所以我们假如我们有两行, 其实可以把第二行的对应数据加到第一行上去, 进行压维操作, 再求一维的最大子段和.
5. 我们要考虑所有的情况, 因此我们以 x 轴作为线段树的区间, 之后来枚举 y 轴, 就可以把所有情况枚举出来.
6. 这题爆 int, 并且我们可以不框住任何矩形, 所以最小值肯定是 0
- #include<iostream>
- #include<algorithm>
- #include<cstring>
- #include<cstdio>
- #include<vector>
- using namespace std;
- typedef long long ll;
- const int N=1e5+10;
- const int inf=0x3f3f3f3f;
- vector<int> xi;
- vector<int> yi;
- struct node{
- int l,r;
- ll sum;
- ll tsum;
- ll lsum;
- ll rsum;
- }tr[N<<2];
- struct qi{
- int x,y;
- ll w;
- }q[N];
- bool cmp(qi a,qi b){
- if(a.y==b.y)
- return a.x<b.x;
- return a.y<b.y;
- }
- void build(int u,int l,int r){
- if(l==r){
- tr[u]={l,l};
- }
- else{
- tr[u]={l,r};
- int mid=l+r>>1;
- build(u<<1,l,mid);
- build(u<<1|1,mid+1,r);
- }
- }
- int findy(int x){
- return lower_bound(yi.begin(),yi.end(),x)-yi.begin()+1;
- }
- int findx(int x){
- return lower_bound(xi.begin(),xi.end(),x)-xi.begin()+1;
- }
- void pushup(int u){
- tr[u].lsum=max(tr[u<<1].lsum,tr[u<<1].sum+tr[u<<1|1].lsum);
- tr[u].rsum=max(tr[u<<1|1].rsum,tr[u<<1|1].sum+tr[u<<1].rsum);
- tr[u].tsum=max(max(tr[u<<1].tsum,tr[u<<1|1].tsum),tr[u<<1].rsum+tr[u<<1|1].lsum);
- tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
- }
- void modify(int u,int w,ll x){
- if(tr[u].l==tr[u].r){
- tr[u].lsum=tr[u].sum=tr[u].rsum=tr[u].tsum=tr[u].sum+x;
- return ;
- }
- else{
- int mid=tr[u].l+tr[u].r>>1;
- if(w<=mid)
- modify(u<<1,w,x);
- else
- modify(u<<1|1,w,x);
- pushup(u);
- }
- }
- int main(){
- int t;
- cin>>t;
- while(t--){
- int n;
- int i;
- cin>>n;
- xi.clear();
- yi.clear();
- for(i=1;i<=n;i++){
- scanf("%d%d%lld",&q[i].x,&q[i].y,&q[i].w);
- xi.push_back(q[i].x);
- yi.push_back(q[i].y);
- }
- sort(q+1,q+n+1,cmp);
- sort(xi.begin(),xi.end());
- xi.erase(unique(xi.begin(),xi.end()),xi.end());
- sort(yi.begin(),yi.end());
- yi.erase(unique(yi.begin(),yi.end()),yi.end());
- int nx=xi.size();
- int ny=yi.size();
- int now=1;
- int k;
- ll ans=0;
- for(i=1;i<=ny;i++){ // 枚举下边界
- build(1,1,nx);
- for(int j=i,k=now;j<=ny;j++){ // 上边界
- while(k<=n&&findy(q[k].y)==j){
- modify(1,findx(q[k].x),q[k].w);
- k++;
- }
- if(j==i)
- now=k;
- ans=max(ans,tr[1].tsum);
- }
- }
- cout<<ans<<endl;
- }
- }
- View Code
来源: http://www.bubuko.com/infodetail-3421490.html