首页 > 代码库 > Zoj 3511 线段树
Zoj 3511 线段树
我们需要维护一个区间和表示各个区间剩下多少个点，每次切一个多边形的时候先算一下被切下来的多边形有多少条边（多少个顶点），然后把这些顶点抹掉即可。
但是会出现一个问题，如果被切下来的多边形还要继续被切，怎么破？ 因为切的顺序是无关的，所以先将所有切的操作排序，先处理切下来小块的，然后处理大块的，就可以避免这个问题了。
#include <cstdio>#include <cstring>#include <iostream>#include <map>#include <set>#include <vector>#include <string>#include <queue>#include <deque>#include <bitset>#include <list>#include <cstdlib>#include <climits>#include <cmath>#include <ctime>#include <algorithm>#include <stack>#include <sstream>#include <numeric>#include <fstream>#include <functional>using namespace std;#define MP make_pair#define PB push_back#define lson rt << 1, l, mid#define rson rt << 1 | 1, mid + 1, rtypedef long long LL;typedef unsigned long long ULL;typedef vector<int> VI;typedef pair<int,int> PII;const int INF = INT_MAX / 3;const double eps = 1e-8;const LL LINF = 1e17;const double DINF = 1e60;const int maxn = 1e4 + 10;int sum[maxn << 2],n,m;PII Q[maxn];void build(int rt,int l,int r) { int mid = (l + r) >> 1; if(l == r) sum[rt] = 1; else { build(lson); build(rson); sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; }}void update(int rt,int l,int r,int ql,int qr) { if(ql <= l && qr >= r) sum[rt] = 0; else { int mid = (l + r) >> 1, lc = rt << 1, rc = rt << 1 | 1; if(sum[rt] == 0) { sum[lc] = sum[rc] = 0; return; } if(ql <= mid) update(lson,ql,qr); if(qr > mid) update(rson,ql,qr); sum[rt] = sum[lc] + sum[rc]; }}int query(int rt,int l,int r,int ql,int qr) { if(ql <= l && qr >= r) return sum[rt]; int mid = (l + r) >> 1,ret = 0; if(sum[rt] == 0) return 0; if(ql <= mid) ret += query(lson,ql,qr); if(qr > mid) ret += query(rson,ql,qr); return ret;} bool cmp(const PII &a, const PII &b) { return abs(a.first - a.second) < abs(b.first - b.second);}int main() { while(scanf("%d%d",&n,&m) != EOF) { build(1,1,n); int ans = 0; for(int i = 0;i < m;i++) { scanf("%d%d",&Q[i].first,&Q[i].second); } sort(Q, Q + m, cmp); for(int i = 0;i < m;i++) { int l = Q[i].first, r = Q[i].second; if(l > r) swap(l,r); ans = max(query(1,1,n,l,r),ans); update(1,1,n,l + 1,r - 1); } ans = max(ans,query(1,1,n,1,n)); printf("%d\n",ans); } return 0;}
Zoj 3511 线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。