【TIOJ 1974】十字射擊（Cross）

原題連結：http://tioj.infor.org/problems/1974
這題是一階的模考題
難度在其中應該是偏易的？

想法在於試著枚舉其中一維度，如果能在極短的時間內求出另一維度的當前最大值就能完成。
矩形只有10^5個，左右界分開看每一維度共有2*10^5個，不難發現座標範圍10^9只是一個叫你離散化的騙局(?)，兩個維度分別真正會出現不同值域的範圍只有2*10^5種而已。
因為要枚舉其中一維度，所以這個維度(我是用x)就不需要離散化，於是先對y座標離散化。

維護y座標的最大值時，可以發現如果硬是把欲枚舉x座標的矩形加進來，對於一個固定的y座標，只要把在其上的矩形加進來最後扣掉重疊的矩形就好。
利用掃描線+線段樹跟著枚舉一起跑，維護好「扣掉重疊矩形」這個動作，就能夠O(1)查詢每個x座標的極值。
線段樹總共被修改2*n次，總共複雜度O(nlgn)

由於題目的權重不存在負值，然後我沒有發現這件事@@
如果有負值的話還要記得額外判斷十字線有一維度完全沒射中的情況，最後和0取MAX應該才是正解。

	#pragma GCC optimize("Ofast")
	#include <iostream>
	#include <algorithm>
	#include <vector>
	#include <string>
	#include <bitset>
	#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	#define pb push_back
	#define ll long long
	using namespace std;
	struct mode
	{
	int place,val,id,type; //type1:L type2:R
	bool operator<(const mode&a)const{
	return place<a.place;
	}
	}qx[200000],qy[200000];
	struct tri
	{
	int L,R,x,Lid,Rid,val;
	bool operator<(const tri&a)const{
	return x<a.x;
	}
	}data[200000];
	int seg[1000000],lazy[1000000],num[200000];
	void build(int l,int r,int rt)
	{
	if(l==r)
	{
	seg[rt]=num[l];
	return;
	}
	int m=(l+r)/2;
	build(l,m,rt*2),build(m+1,r,rt*2+1);
	seg[rt]=max(seg[rt*2],seg[rt*2+1]);
	}
	void push(int l,int r,int rt)
	{
	if(!lazy[rt] || l==r) return;
	seg[rt*2]+=lazy[rt],seg[rt*2+1]+=lazy[rt],lazy[rt*2]+=lazy[rt],lazy[rt*2+1]+=lazy[rt];
	lazy[rt]=0;
	}
	void modify(int L,int R,int l,int r,int rt,int val)
	{
	push(l,r,rt);
	if(L<=l && R>=r)
	{
	seg[rt]+=val,lazy[rt]+=val;
	return ;
	}
	int m=(l+r)/2;
	if(L<=m) modify(L,R,l,m,rt*2,val);
	if(R>m) modify(L,R,m+1,r,rt*2+1,val);
	seg[rt]=max(seg[rt*2],seg[rt*2+1]);
	}
	int main()
	{jizz
	int n,x1,y1,x2,y2,val,top,now,bomb,ans=0,i;
	cin >> n;
	for(i=0;i<n;i++)
	{
	cin >> x1 >> y1 >> x2 >> y2 >> val;
	data[i*2]=tri{y1,y2,x1,0,0,-val},data[i*2+1]=tri{y1,y2,x2+1,0,0,val};
	qx[i*2]=mode{x1,val,0,0},qx[i*2+1]=mode{x2+1,-val,0,0};
	qy[i*2]=mode{y1,val,i,0},qy[i*2+1]=mode{y2,-val,i,1};
	}
	sort(qx,qx+2*n),sort(qy,qy+2*n);
	for(i=0,top=-1,now=-1,val=0,bomb=0;i<2*n;i++)
	{
	if(qy[i].place!=now) (top==-1) ? 0 : num[top]=val,++top,now=qy[i].place,val+=bomb,bomb=0;
	if(!qy[i].type) val+=qy[i].val,data[qy[i].id*2].Lid=top,data[qy[i].id*2+1].Lid=top;
	else bomb+=qy[i].val,data[qy[i].id*2].Rid=top,data[qy[i].id*2+1].Rid=top;
	}
	build(0,2*n-1,1),sort(data,data+2*n);
	for(i=0,val=0,now=-1,top=0;i<2*n;i++)
	{
	if(qx[i].place!=now)
	ans=max(val+seg[1],ans),now=qx[i].place,ans=max(val,ans);
	val+=qx[i].val;
	while(top<2*n && data[top].x<=now) modify(data[top].Lid,data[top].Rid,0,2*n-1,1,data[top].val),++top;
	}
	cout << ans << "\n";
	}

view raw gistfile1.txt hosted with ❤ by GitHub