锐客网

  1. 首页 > 睿知 > it技术 > >

HHappy Triangle（询问是否构成三角形）

IT知识三角形happyTriangle

将相本无种，男儿当自强。这篇文章主要讲述HHappy Triangle（询问是否构成三角形）相关的知识，希望能为你提供帮助。
题:https://ac.nowcoder.com/acm/contest/5667/H
题意：给定空的容器multiset：MS,有q个操作，操作一为向MS中加入x，操作二为在MS删除x，操作三为询问在MS是否存在a，b与x能形成一个不退化的三角形。
分析：对于询问操作，有俩种情况，情况一是x作为最大边，这种情况只要判断在MS中小于等于x的最大的俩个数来判断能否形成三角形，用一个set容器即可搞定；
情况二为x不作为最大边，假设有a< =b满足条件，因为这种情况b肯定比x大，而a在越接近于b的情况下，x，a，b更容易满足条件，转化为b-a越小越能满足条件，所以这中情况，只要找x后缀中与前驱a之差最小的值ans，若ans< x说明存在，否则不存在，这部分可以用线段树解决。
【HHappy Triangle（询问是否构成三角形）】而操作一和操作二根据线段树值的确立来进行相应的操作即可。
（记得开ll）

HHappy Triangle（询问是否构成三角形）

文章图片
HHappy Triangle（询问是否构成三角形）

文章图片
#include< bits/stdc++.h> using namespace std; #define pb push_back #define MP make_pair #define lson root< < 1,l,midd #define rson root< < 1|1,midd+1,r typedef long long ll; const int mod=1e9+7; const int M=2e5+5; const ll inf=1e18; ll tr[M< < 2],lisan[M],cnt[M],a[M],op[M],m; multiset< ll> MS; void pn(){ puts("No"); } void py(){ puts("Yes"); } void up(int root){ tr[root]=min(tr[root< < 1],tr[root< < 1|1]); } void build(int root,int l,int r){ tr[root]=inf; ///cout< < l< < " "< < r< < endl; if(l==r) return ; int midd=(l+r)> > 1; build(lson); build(rson); } void update(int pos,ll c,int root,int l,int r){ if(l==r){ tr[root]=c; return ; } int midd=(l+r)> > 1; if(pos< =midd) update(pos,c,lson); else update(pos,c,rson); up(root); } ll query(int L,int R,int root,int l,int r){ if(L< =l& & r< =R) return tr[root]; int midd=(l+r)> > 1; ll minn=inf; if(L< =midd) minn=min(minn,query(L,R,lson)); if(R> midd) minn=min(minn,query(L,R,rson)); return minn; }void solve1(int x){ int pos=lower_bound(lisan+1,lisan+1+m,x)-lisan; if(cnt[pos]){ update(pos,0,1,1,m); } else{ auto it=MS.lower_bound(x); auto tmp=it; ///更新当前插入位 it--; update(pos,x-*it,1,1,m); ///更新当前插入位的后一位 int pos2=lower_bound(lisan+1,lisan+1+m,*tmp)-lisan; if(cnt[pos2]< 2) update(pos2,*tmp-x,1,1,m); } cnt[pos]++; MS.insert(x); } void solve2(int x){ int pos=lower_bound(lisan+1,lisan+1+m,x)-lisan; if(cnt[pos]==2){ auto it=MS.lower_bound(x); it--; update(pos,x-*it,1,1,m); } else if(cnt[pos]==1){ update(pos,inf,1,1,m); auto pre=MS.lower_bound(x); pre--; auto las=MS.upper_bound(x); int pos2=lower_bound(lisan+1,lisan+1+m,*las)-lisan; if(cnt[pos2]< 2){ update(pos2,*las-*pre,1,1,m); } } cnt[pos]--; ///因为只删一个，所以不能直接删除 auto it=MS.lower_bound(x); MS.erase(it); } void solve3(int x){ ///x作为最大边 auto it=MS.upper_bound(x); it--; if(it!=MS.begin()){ auto tmp=it; it--; if(*tmp+*it> x){ py(); return ; } } ///x不作为最大边 it=MS.upper_bound(x); int pos=lower_bound(lisan+1,lisan+1+m,*it)-lisan; if(query(pos,m,1,1,m)< x) py(); else pn(); return ; } int main(){ int n,tot=0; scanf("%d",& n); for(int i=1; i< =n; i++){ scanf("%d%d",& op[i],& a[i]); lisan[++tot]=a[i]; } lisan[++tot]=inf,lisan[++tot]=-inf; sort(lisan+1,lisan+1+tot); m=unique(lisan+1,lisan+1+tot)-lisan-1; MS.insert(inf),MS.insert(-inf); build(1,1,m); for(int i=1; i< =n; i++){ if(op[i]==1)solve1(a[i]); else if(op[i]==2)solve2(a[i]); else solve3(a[i]); } return 0; }

View Code 

    推荐阅读


    上一篇：对于app监测root权限或者强制升级

    下一篇：appium自动化测试之H5页面测试