[TIOJ] 1316. 晶片設計

題目連結:http://tioj.infor.org/problems/1316

---

一開始想錯方向，以為是有一堆開頭跟結尾，然後要選一些之類的...。卡了超久做不出來後，才發現其實它就是一堆線段，然後要選一堆線段，使得同一個位置只能最多被覆蓋到兩次。那其實就直接greedy選右界最靠近左邊的就好了(因為越短，表示你越可以選到後面的)。
這裡寫了個線段樹，來判斷可不可以插入，不過應該可以不用，然後也可以直接$O(N)$的做這個操作XD

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define FF first
#define SS second

const int N = 4000 + 5;

class SegTre{
	private:
		struct node{
			int flag=0, val=0;
		} nodes[N<<3];
		int size;
		inline int lc(int x){return 2*x+1;}
		inline int rc(int x){return 2*x+2;}
		inline void push(int l, int r, int id){
			if(r-l > 1){
				nodes[lc(id)].flag+=nodes[id].flag;
				nodes[rc(id)].flag+=nodes[id].flag;
			}
			nodes[id].val += nodes[id].flag;
			nodes[id].flag=0;
		}
		inline void pull(int id){
			nodes[id].val = max(nodes[lc(id)].val+nodes[lc(id)].flag, \
				nodes[rc(id)].val+nodes[rc(id)].flag);
		}
		int query(int ql, int qr, int l, int r, int id){
			if(qr <= l or r <= ql) return 0;
			push(l,r,id);
			if(ql <= l and r <= qr) return nodes[id].val;
			int mid = (l+r)>>1;
			return max(query(ql,qr,l,mid,lc(id)), \
				query(ql,qr,mid,r,rc(id)));
		}
		void modify(int ql, int qr, int l, int r, int v, int id){
			if(qr <= l or r <= ql) return;
			push(l,r,id);
			if(ql <= l and r <= qr){
				nodes[id].flag=v;
				return;
			}
			int mid=(l+r)>>1;
			modify(ql,qr,l,mid,v,lc(id));
			modify(ql,qr,mid,r,v,rc(id));
			pull(id);
		}
	public:
		void build(int* arr, int n){
			size=n;
		}
		int query(int l, int r){
			return query(l, r, 0, size, 0);
		}
		void modify(int l, int r, int v){
			modify(l, r, 0, size, v, 0);
		}
} seg;

int arr[N<<1];
PII pos[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	fill(pos,pos+n+1,(PII){-1,-1});
	for(int i=0;i<(n<<1);i++){
		cin>>arr[i];
		if(pos[arr[i]].FF==-1) pos[arr[i]].FF = i;
		else pos[arr[i]].SS = i;
	}
	seg.build(arr, (n<<1) + 3);
	sort(pos+1,pos+n+1,[](PII a, PII b){return a.SS<b.SS;});
	int ans = 0;
	for(int i=1;i<=n;i++){
		if(seg.query(pos[i].FF, pos[i].SS+1) < 2){
			ans++;
			seg.modify(pos[i].FF, pos[i].SS+1, 1);
		}
	}
	cout<<ans<<'\n';
	return 0;
}