锐客网

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

[nowcoder5667H]Happy Triangle

IT知识nowcoder

【[nowcoder5667H]Happy Triangle】吾生也有涯,而知也无涯。这篇文章主要讲述[nowcoder5667H]Happy Triangle相关的知识，希望能为你提供帮助。
可以发现合法的答案有两种可能： 1.询问的$x$即为最大值（或之一），那么只需要找到x前两个数并判断即可 2.询问的$x$不是最大值，那么就要保证另外两边之差小于$x$，维护后缀中$的前驱k-k的前驱$最小的数即可，可以使用线段树 然而这道题还有很多的细节： 1.这里的前驱可以与k相等（因为$x,k,k$（$k> x$）也可以），因此在插入后从1变成2同样也要修改（同理删除2变成1） 2.但修改时找前驱需要找到第一个比他小的，然后它的后继同样也要修改 3.$x$的前两个数有三种可能：$x,x,x$、$x,x,y$、$x,y,z$，需要分类讨论（比如有1个x，那么就需要根据个数来查询）

[nowcoder5667H]Happy Triangle

文章图片
[nowcoder5667H]Happy Triangle

文章图片
1 #include< bits/stdc++.h> 2 using namespace std; 3 #define N 200005 4 #define oo 0x3f3f3f3f 5 #define mid (l+r> > 1) 6 #define T r,1,1e9 7 int V,r,n,p,k,ls[N*30],rs[N*30],sum[N*30],f[N*30]; 8 int add(int & k,int l,int r,int x,int y){ 9if (!k)k=++V; 10sum[k]+=y; 11if (l==r)return sum[k]; 12if (x< =mid)return add(ls[k],l,mid,x,y); 13return add(rs[k],mid+1,r,x,y); 14 } 15 int find1(int k,int l,int r,int x){ 16if ((!x)||(!sum[k]))return -oo; 17if (l==r)return l; 18if (x< =mid)return find1(ls[k],l,mid,x); 19int ans=find1(rs[k],mid+1,r,x); 20if ((ans> 0)||(!sum[ls[k]]))return ans; 21return find1(ls[k],l,mid,x); 22 } 23 int find2(int k,int l,int r,int x){ 24if ((x> 1e9)||(!sum[k]))return oo; 25if (l==r)return l; 26if (mid< x)return find2(rs[k],mid+1,r,x); 27int ans=find2(ls[k],l,mid,x); 28if ((ans!=oo)||(!sum[rs[k]]))return ans; 29return find2(rs[k],mid+1,r,x); 30 } 31 void update(int k,int l,int r,int x,int y){ 32if (l==r){ 33f[k]=y; 34return; 35} 36if (x< =mid)update(ls[k],l,mid,x,y); 37else update(rs[k],mid+1,r,x,y); 38f[k]=min(f[ls[k]],f[rs[k]]); 39 } 40 int query(int k,int l,int r,int x,int y){ 41if ((!k)||(l> y)||(x> r))return oo; 42if ((x< =l)& & (r< =y))return f[k]; 43return min(query(ls[k],l,mid,x,y),query(rs[k],mid+1,r,x,y)); 44 } 45 int main(){ 46scanf("%d",& n); 47memset(f,oo,sizeof(f)); 48for(int i=1; i< =n; i++){ 49scanf("%d%d",& p,& k); 50int x=find1(T,k-1),y=find2(T,k+1); 51if (p< 3){ 52int t=add(T,k,3-2*p); 53if ((p==1)& & (t==2))update(T,k,0); 54if ((p==2)& & (t==1))update(T,k,k-x); 55if ((p==1)& & (t==1)){ 56update(T,k,k-x); 57if ((y!=oo)& & (add(T,y,0)==1))update(T,y,y-k); 58} 59if ((p==2)& & (t==0)){ 60update(T,k,oo); 61if ((y!=oo)& & (add(T,y,0)==1))update(T,y,y-x); 62} 63} 64else{ 65int t=add(T,k,0); 66if ((t> 1)||((x> 0)& & ((t==1)||(2*x-query(T,x,x)> k)))){ 67printf("Yes "); 68continue; 69} 70if (query(T,y,1e9)< k)printf("Yes "); 71else printf("No "); 72} 73} 74 }

View Code 

    推荐阅读


    上一篇：Android使用selector切换enable状态遇到的问题（只改变了颜色但是没改变形状）

    下一篇：appium-Hybird应用自动化