一个问题

回复帖子

@GOOBA 2020-08-22 13:05 回复

蒟蒻初学扫描线, 一开始没想到后来看了题解自己写,写完发现只有80分,后来与题解疯狂对比,找不到实质上的不同(我感觉),然后来看贴,发现要把tot改成2 * n , 但是题解却写的是tot诶,为什么? 以下是题解代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define mid ((l+r)>>1)
using namespace std;

const int maxn=1e4+10;
int n,tot,w,h;
int yy[maxn<<1];                    //离散化的y轴 
int rm[maxn<<3],flag[maxn<<3];      //rm表示区间最大值,flag为懒标记 八倍数组,因为2n条线段,线段树要4倍。 
struct seg
{
    int x,y1,y2,c;
    seg(){}
    seg(int xx,int yy1,int yy2,int cc){x=xx,y1=yy1,y2=yy2,c=cc;}
}line[maxn<<1];

bool cmp(const seg &a,const seg &b)//这里注意排序,x相同时先处理入边 
{
    if(a.x==b.x)return a.c>b.c;
    return a.x<b.x;
}
void pushdown(int t,int l,int r)//下传懒标记 
{
    if(flag[t]==0)return;
    rm[t]+=flag[t];
    if(l!=r)        //这里主要防止越界 
    {
        flag[t<<1]+=flag[t];
        flag[t<<1|1]+=flag[t];
    }
    flag[t]=0;
}
void modify(int t,int l,int r,int x,int y,int z)//区间修改 
{
    if(x<=l&&r<=y)
    {
        flag[t]+=z;
        return;
    }
    if(x<=mid)modify(t<<1,l,mid,x,y,z);
    if(y>mid)modify(t<<1|1,mid+1,r,x,y,z);
    pushdown(t<<1,l,mid);
    pushdown(t<<1|1,mid+1,r);
    rm[t]=max(rm[t<<1],rm[t<<1|1]); //回传最值 
}
int main()
{
    int t=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d %d",&n,&w,&h);
        memset(rm,0,sizeof(rm));
        memset(flag,0,sizeof(flag));
        for(int i=1;i<=n;i++)
        {
            int x=0,y=0,c=0;
            scanf("%d %d %d",&x,&y,&c);
            line[i]=seg(x,y,y+h-1,c);
            line[i+n]=seg(x+w-1,y,y+h-1,-c);
            yy[i]=y+h-1;
            yy[i+n]=y;
        }
        n<<=1;//处理的是2n条线段 
        sort(yy+1,yy+1+n);//排序 
        tot=unique(yy+1,yy+1+n)-yy-1;//去重 
        sort(line+1,line+1+n,cmp);//根据横坐标排序 
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            int l=lower_bound(yy+1,yy+1+tot,line[i].y1)-yy;//二分离散化 
            int r=lower_bound(yy+1,yy+1+tot,line[i].y2)-yy;
           modify(1,1,tot,l,r,line[i].c);        ans=max(ans,rm[1]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

我的代码

#include<bits/stdc++.h>
using namespace std ;
#define int long long
#define kkksc signed main
#define ddd double
#define maxn 1000010
#define lc o << 1
#define rc ((o << 1) | 1 )
#define mem(x) memset(x , 0 , sizeof(x))
//#define mid ((l + r) >> 1)
int read(){
    int ans = 0 , f = 1 ; char ch = getchar() ;
    while(ch < '0' || ch > '9'){ if(ch == '-') f = -1 ; ch = getchar() ; }
    while(ch >= '0' && ch <= '9') {
        ans = (ans * 10) + ch - '0' ;
        ch = getchar() ;
    }
    return ans * f ;
}
int n , w , h ; 
struct scanline{
    int l , r, h , val;
    bool operator <(const scanline &x) const {return h == x.h ? val > x.val : h < x.h ;}
}line[maxn];
int maxx[maxn << 3] , tag[maxn << 3] ; 
int yy[maxn << 3] ; 
inline void pushup(int o){
    maxx[o] = max(maxx[lc] , maxx[rc]) ; 
    return  ;
}
inline void pushdown(int o){
    maxx[lc] += tag[o] ; maxx[rc] += tag[o] ; 
    tag[lc] += tag[o] ; tag[rc] += tag[o] ; 
    tag[o] = 0 ; 
    return ; 
}
inline void change(int o , int l , int r , int ql , int qr , int k){
//  printf("l : %lld r : %lld ql : %lld qr : %lld \n", l , r , ql ,qr) ; 
    if(ql > r || qr < l) return ; 
    if(ql <= l && r <= qr){
//      printf("will change : l : %lld r : %lld ql : %lld qr : %lld \n", l , r , ql ,qr) ; 
        maxx[o] += k ; 
        tag[o] += k ; 
        return ; 
    }
    int mid = (l + r) >> 1 ; 
    if(tag[o]) pushdown(o);
    change(lc , l , mid , ql , qr , k) ; 
    change(rc , mid + 1 , r , ql ,qr , k) ; 
    pushup(o) ;
    return ; 
}
int t ; 
void clear(){
    mem(maxx) , mem(tag) ; 
} 
kkksc(){
//  freopen("test.in" , "r" , stdin) ;
//  freopen("test.out" , "w"  , stdout) ;
    t = read() ; 
    while(t--){
        n = read() , w = read() - 1 , h = read() - 1; 
        for(int i = 1 ; i <= n ; i++){
            int x = read() , y = read() , l = read() ; 
            line[i * 2 - 1] = (scanline){y , y + h , x , l} ; 
            line[i * 2] = (scanline){y , y + h , x + w , -l} ; 
            yy[i * 2 - 1] = y ; 
            yy[i * 2] = y + h ; 
        }
        n *= 2 ; 
        sort(yy + 1 , yy + 1 + n) ;
        sort(line + 1 , line + 1 + n) ; 
        int ans = 0 ; 
        int tot = unique(yy + 1 , yy + 1 + n) - yy - 1 ; 
        for(int i = 1 ; i <= n ; i++){
            int l = lower_bound(yy+1,yy+1+n , line[i].l  ) - yy; 
            int r = lower_bound(yy+1,yy+1+n , line[i].r ) - yy ;
            change(1 , 1 , tot , l , r , line[i].val ); 
            ans = max(ans , maxx[1]) ; 
        }
        cout << ans << endl ; 
        clear() ; 
    }
}

问题出在这里

题解的代码:
modify(1,1,tot,l,r,line[i].c);//修改,这里注意是l和r,一开始我写的r-1竟然对了9个(但实际上是错误的) 
我的代码:
change(1 , 1 , tot , l , r , line[i].val ); 
把tot改成n就过了。。。。
@GOOBA 2020-08-22 13:19 回复 举报

对拍了一个小时了也没找到错误。。。。。(数据生成器来自之前的帖子)

@GOOBA 2020-08-22 17:44 回复 举报

@913887524gsd !!!!!!!!!发现问题 感谢(一直在看线段树和其他的,果然还是低估了自己的愚蠢程度)

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。