有点不懂这道题
查看原帖
有点不懂这道题
944873
dxy19213987956楼主2024/7/22 22:03

我自己写的代码在洛谷上过了,去交hdu就wa,然后我找了一个讲hdu上这道题的博客,把他的代码复制交到hdu上过了,然后拿来交洛谷最后一个点wa,不知道啥情况 我的代码:

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

constexpr int maxn = 1e4 + 5;

struct ScanLine {
    int ly = 0, ry = 0, x = 0, val = 0;
    // ScanLine(int lx = 0, int rx = 0, int x = 0, int val = 0) : ly(ly), ry(ry), x(x), val(val) {}
    bool operator<(const ScanLine& b) const { return x < b.x || x == b.x && val > b.val; }
};

struct Info {
    int len = 0, cnt = 0, num = 0;
    bool ls = false, rs = false;
    Info(int len = 0, int cnt = 0, int num = 0, bool ls = 0, bool rs = 0)
        : len(len), cnt(cnt), num(num), ls(ls), rs(rs) {}
    void clear() { len = cnt = num = ls = rs = 0; }
} info[maxn << 2];

vector<int> b;

void build(int p, int l, int r) {
    info[p].clear();
    if (r - l == 1) return;
    int mid = (l + r) >> 1;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid, r);
}

void pushup(int p, int l, int r) {
    if (info[p].cnt) {
        info[p].len = b[r] - b[l];
        info[p].ls = info[p].rs = true;
        info[p].num = 1;
    } else {
        info[p].len = info[p * 2].len + info[p * 2 + 1].len;
        info[p].ls = info[p * 2].ls;
        info[p].rs = info[p * 2 + 1].rs;
        info[p].num =
            info[p * 2].num + info[p * 2 + 1].num - (info[p * 2].rs && info[p * 2 + 1].ls);
    }
}

void update(int p, int l, int r, int x, int y, int v) {
    if (l >= y || r <= x) {
        return;
    }
    if (x <= l && r <= y) {
        info[p].cnt += v;
        pushup(p, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    update(p * 2, l, mid, x, y, v);
    update(p * 2 + 1, mid, r, x, y, v);
    pushup(p, l, r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    while (cin >> n) {
        vector<ScanLine> line;
        b.clear();
        for (int i = 0; i < n; i++) {
            int x1, x2, y1, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            // cerr << x1 << " " << x2 << " " << y1 << " " << y2 << "\n";
            b.emplace_back(y1);
            b.emplace_back(y2);
            line.push_back({y1, y2, x1, 1});
            line.push_back({y1, y2, x2, -1});
        }
        sort(b.begin(), b.end());
        sort(line.begin(), line.end());
        int cnt = b.erase(unique(b.begin(), b.end()), b.end()) - b.begin();
        build(1, 0, cnt);
        int res = 0, lst = 0;
        n *= 2;
        for (int i = 0; i < n - 1; i++) {
            int l = lower_bound(b.begin(), b.end(), line[i].ly) - b.begin();
            int r = lower_bound(b.begin(), b.end(), line[i].ry) - b.begin();
            // cerr << line[i].ly << " " << line[i].ry << "\n";
            // cerr << "l = " << l << " r = " << r << "\n";
            update(1, 0, cnt, l, r, line[i].val);
            res += abs(lst - info[1].len);
            lst = info[1].len;
            res += (line[i + 1].x - line[i].x) * (info[1].num << 1);
            // cerr << res << "\n";
        }
        res += line[n - 1].ry - line[n - 1].ly;
        cout << res << "\n";
    }
    return 0;
}

博客代码:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <string>
#include <math.h>
#include <stack>
const int maxn=1e5+7;
#define mod 998244353
#define Lson l,m,rt<<1
#define Rson m+1,r,rt<<1|1
typedef long long ll;
using namespace std;
int mi,mx;
int n;
struct Edeg
{
    double l,r,h;
    int flag;
    Edeg()=default;
    Edeg(double a,double b,double c,int d):l(a),r(b),h(c),flag(d){}
    bool operator < (const Edeg &a) const
    {
        return h<a.h;
    }
}edge[maxn*3];
struct Tree
{
    int l,r;
    double len;
    int lazy;
    bool lc,rc;
    int num;
}tree[maxn<<2];
void Build(int l,int r,int rt)
{
    tree[rt].l=l,tree[rt].r=r;
    tree[rt].lazy=tree[rt].lc=tree[rt].rc=0;
    tree[rt].num=tree[rt].len=0;
    if(l==r) return;
    int m=(l+r)>>1;
    Build(Lson);
    Build(Rson);
}
void push_up(int rt)
{
    if(tree[rt].lazy)
    {
        tree[rt].len=tree[rt].r-tree[rt].l+1;
        tree[rt].lc=tree[rt].rc=1;
        tree[rt].num=1;
    }
    else if(tree[rt].l==tree[rt].r)
    {
        tree[rt].len=tree[rt].num=0;
        tree[rt].lc=tree[rt].rc=0;
    }
    else
    {
        tree[rt].len=tree[rt<<1].len+tree[rt<<1|1].len;
        tree[rt].lc=tree[rt<<1].lc,tree[rt].rc=tree[rt<<1|1].rc;
        tree[rt].num=tree[rt<<1].num+tree[rt<<1|1].num-(tree[rt<<1].rc&tree[rt<<1|1].lc);
    }
}
void updata(int L,int R,int v,int l,int r,int rt)
{
    if(L<=l&&R>=r)
    {
        tree[rt].lazy+=v;
        push_up(rt);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m) updata(L,R,v,Lson);
    if(R>m)  updata(L,R,v,Rson);
    push_up(rt);
}
 
int main(int argc, char const *argv[])
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    double x1,y1,x2,y2;
    while(scanf("%d",&n)!=EOF)
    {
        mi=maxn,mx=-maxn;
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            edge[i*2]=Edeg(x1,x2,y1,1);
            edge[i*2+1]=Edeg(x1,x2,y2,-1);
            if(x1>mx) mx=x1;
            if(x2>mx) mx=x2;
            if(x1<mi) mi=x1;
            if(x2<mi) mi=x2;
        }
        sort(edge,edge+2*n);
        double ans=0;
        double last=0;
        Build(mi,mx-1,1);//有个0
        for(int i=0;i<2*n;i++)
        {
            updata(edge[i].l,edge[i].r-1,edge[i].flag,mi,mx-1,1);
            ans+=fabs(tree[1].len-last);
            ans+=(edge[i+1].h-edge[i].h)*2*tree[1].num;
            last=tree[1].len;
        }
        printf("%.0f\n",ans);
    }
}
2024/7/22 22:03
加载中...