[TIOJ]1974. 十字射擊（Cross）

題目連結：http://tioj.ck.tp.edu.tw/problems/1974

不難發現可以利用掃描線的方法，掃過x軸，就能知道選擇x軸第 i 點會垂直經過哪些矩形，這時只要找出那從哪個點 j 水平發射會經過矩形價值總合對大，因為也要考慮到垂直已經算進去的那些矩形，所以可以用線段樹維護區間加值、區間詢問。

#include <iostream>
#include <algorithm>
#include <bitset>
#include <queue>
#include <vector>
#define lld long long
#define PB push_back
#define F first
#define S second
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
#define endl '\n'
#define N 100005
#define M (l+r)/2
using namespace std;
typedef pair<int,int> Pair;
vector<int> vx,vy,ouch[2*N];
int X1[N],X2[N],Y1[N],Y2[N],w[N],n,m;
bitset<N> in;
struct Node{
    int w,tag;
}seg[11*N];
inline void pull(int id){
    seg[id].w = max(seg[id << 1].w,seg[id << 1|1].w);
}
inline void push(int id){
    if(seg[id].tag == 0)return;
    seg[id << 1].w += seg[id].tag;
    seg[id << 1].tag += seg[id].tag;
    seg[id << 1|1].w += seg[id].tag;
    seg[id << 1|1].tag += seg[id].tag;
    seg[id].tag = 0;
}
void update(int l,int r,int ll,int rr,int k,int id){
    if(r < ll || l > rr)return;
    push(id);
    if(l >= ll && r <= rr){
        seg[id].w += k;
        seg[id].tag += k;
        return;
    }
    update(l,M,ll,rr,k,id << 1);
    update(M+1,r,ll,rr,k,id << 1|1);
    pull(id);
}
int query(int l,int r,int ll,int rr,int id){
    if(r < ll || l > rr)return -1;
    push(id);
    if(l >= ll && r <= rr)return seg[id].w;
    return max(query(l,M,ll,rr,id << 1),query(M+1,r,ll,rr,id << 1|1));
}
int main(){jizz
    cin >> m;
    for(int i = 0 ; i < m; i++){
        cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i] >> w[i];
        X2[i]++;
        vx.PB(X1[i]);vx.PB(X2[i]);
        vy.PB(Y1[i]);vy.PB(Y2[i]);
    }
    sort(vx.begin(),vx.end());vx.resize(unique(vx.begin(),vx.end())-vx.begin());
    sort(vy.begin(),vy.end());vy.resize(unique(vy.begin(),vy.end())-vy.begin());
    n = vy.size()-1;
    for(int i = 0 ; i < m ; i++){
        X1[i] = lower_bound(vx.begin(),vx.end(),X1[i])-vx.begin();
        X2[i] = lower_bound(vx.begin(),vx.end(),X2[i])-vx.begin();
        Y1[i] = lower_bound(vy.begin(),vy.end(),Y1[i])-vy.begin();
        Y2[i] = lower_bound(vy.begin(),vy.end(),Y2[i])-vy.begin();
        ouch[X1[i]].PB(i);
        ouch[X2[i]].PB(i);
        update(0,n,Y1[i],Y2[i],w[i],1);
    }
    int ans = -1,tmp = 0;
    for(int i = 0 ; i < vx.size() ; i++){
        for(int j : ouch[i]){
            if(in[j])update(0,n,Y1[j],Y2[j],w[j],1),in[j] = 0,tmp -= w[j];
            else update(0,n,Y1[j],Y2[j],-w[j],1),in[j] = 1,tmp += w[j];
        }
        ans = max(ans,tmp + seg[1].w);
    }
    cout << ans << endl;
    return 0;
}