[TIOJ] 1316. 晶片設計
題目連結:http://tioj.infor.org/problems/1316
一開始想錯方向，以為是有一堆開頭跟結尾，然後要選一些之類的...。卡了超久做不出來後，才發現其實它就是一堆線段，然後要選一堆線段，使得同一個位置只能最多被覆蓋到兩次。那其實就直接greedy選右界最靠近左邊的就好了(因為越短，表示你越可以選到後面的)。
這裡寫了個線段樹，來判斷可不可以插入，不過應該可以不用，然後也可以直接$O(N)$的做這個操作XD
一開始想錯方向，以為是有一堆開頭跟結尾，然後要選一些之類的...。卡了超久做不出來後，才發現其實它就是一堆線段，然後要選一堆線段，使得同一個位置只能最多被覆蓋到兩次。那其實就直接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;
}
留言
張貼留言