Main » 2013 September 12 » 区间序成功了[庆祝一下](hdu1540)
4:55 PM 区间序成功了[庆祝一下](hdu1540) |
HDU1540 这道题真是烦新研究的区间序 struct seg { int l,r; bool operator <(const seg a)const { if ((a.l<=l)&&(r<=a.r)) return 0; if ((l<=a.l)&&(a.r<=r)) return 0; if (r<a.l) return 1; if (a.r<l) return 0; } }; 事实证明， set在区间合并题中已经具有了代替线段树的能力 不过区间合并很坑爹 要讨论的情况很多 插入一个点: (last)为要插入的点 it2=it1=it;it1--;it2++; if (((*it1).r==last-1)&&((*it2).l==last+1)) { tt.l=(*it1).l,tt.r=(*it2).r; list.erase(*it);list.erase(*it1);list.erase(*it2); list.insert(tt); continue; } if (((*it1).r==last-1)&&((*it2).l!=last+1)) { tt.l=(*it1).l,tt.r=last; list.erase(*it);list.erase(*it1);list.insert(tt); continue; } if (((*it1).r!=last-1)&&((*it2).l==last+1)) { tt.l=last,tt.r=(*it2).r; list.erase(*it);list.erase(*it2);list.insert(tt); continue; } } if ((it==list.begin())&&(next(it)!=list.end())) { it2=it;it2++; if ((*it2).l==last+1) { tt.l=last,tt.r=(*it2).r; list.erase(*it);list.erase(*it2);list.insert(tt); continue; } } 关键是区间序的定义 1 struct seg 2 { 3 int l,r; 4 bool operator <(const seg a)const 5 { 6 if ((a.l<=l)&&(r<=a.r)) return 0; 7 if ((l<=a.l)&&(a.r<=r)) return 0; 8 if (r<a.l) return 1; 9 if (a.r<l) return 0; 10 } 11}; 第6-7行是根据set的原理来定义的 这个cmp满足了 严格的弱序化’(strick weak ordering)”。 什么是严格的弱序化？让我们看看wiki上的定义： 严格弱序化拥有如下属性。对于集合S中所有的x，y，z， 对于所有的x，不存在x < x （非自反性 - 21条标题说的就是这个） 对于所有x不等于y，如果x < y那么不存在y < x （不对称性） 对于所有的x，y和z，如果x < y并且y < z，那么x < z（传递性） 如果x < y，那么对于所有的z，要么x < z要么z < y（或者两者都成立） 附上全部code: #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<set> #define ittype set<seg>::iterator #define M 200010 using namespace std; struct seg { int l,r; bool operator <(const seg a)const { if ((a.l<=l)&&(r<=a.r)) return 0; if ((l<=a.l)&&(a.r<=r)) return 0; if (r<a.l) return 1; if (a.r<l) return 0; } }; ittype next(ittype a) { a++; return a; }; seg t,b,tt,t1,t2; ittype it1,it2; multiset<seg> list; int n,m,ans,d; int T[M]; void Main() { memset(T,0,sizeof(T)); list.clear(); t.l=1,t.r=n; char op; list.insert(t); int L=0,i; for (i=1;i<=m;i++) { cin>>op; if (op=='D') { cin>>d; L++;T[L]=d; t.l=d,t.r=d; ittype it=list.find(t); if (it==list.end()) continue; b=*it; list.erase(b); if (b.l<b.r) { if (d==b.r) {tt=b;tt.r--;list.insert(tt);} else if (d==b.l) {tt=b;tt.l++;list.insert(tt);} else { t1.l=b.l,t1.r=d-1; t2.r=b.r,t2.l=d+1; list.insert(t1); list.insert(t2); } } } if (op=='Q') { cin>>d;t.l=t.r=d; ittype it=list.find(t); if (it==list.end()) ans=0; else if (!(((*it).l<=d)&&(d<=(*it).r))) ans=0; else ans=(*it).r-(*it).l+1; printf("%d\n",ans); } if (op=='R') { int last=T[L];L--; t.l=last,t.r=last; ittype it2,it1,itt,it; it=list.insert(t); if ((it!=list.begin())&&(next(it)!=list.end())) { it2=it1=it;it1--;it2++; if (((*it1).r==last-1)&&((*it2).l==last+1)) { tt.l=(*it1).l,tt.r=(*it2).r; list.erase(*it);list.erase(*it1);list.erase(*it2); list.insert(tt); continue; } if (((*it1).r==last-1)&&((*it2).l!=last+1)) { tt.l=(*it1).l,tt.r=last; list.erase(*it);list.erase(*it1);list.insert(tt); continue; } if (((*it1).r!=last-1)&&((*it2).l==last+1)) { tt.l=last,tt.r=(*it2).r; list.erase(*it);list.erase(*it2);list.insert(tt); continue; } } if ((it==list.begin())&&(next(it)!=list.end())) { it2=it;it2++; if ((*it2).l==last+1) { tt.l=last,tt.r=(*it2).r; list.erase(*it);list.erase(*it2);list.insert(tt); continue; } } if ((it!=list.begin())&&(next(it)==list.end())) { it1=it;it1--; if ((*it1).r==last-1) { tt.l=(*it1).l,tt.r=last; list.erase(*it);list.erase(*it1);list.insert(tt); continue; } } } } } int main() { ios::sync_with_stdio(false); while (cin>>n>>m) Main(); } |
|
|
| Total comments: 0 | |