我自己写的代码在洛谷上过了,去交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);
}
}