差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:namespace:牛客多校第六场 [2020/07/29 17:32]
great_designer [H]
+++ 2020-2021:teams:namespace:牛客多校第六场 [2020/08/01 10:22] (当前版本)
great_designer [I]
@@ 行 165: / 行 165: @@
 以下是补题。
+本题用到了斐波那契数和卢卡斯数的结论。[[斐波那契和卢卡斯]]
 <hidden>
-<code C>
+<code C++>
+#include<stdio.h>
+#include<algorithm>
+#include<set>
+using namespace std;
+set<pair<int,int> > s;
+long long L[44],ans;
+void Sub(set<pair<int,int> >::iterator p)
+{
+    set<pair<int,int> >::iterator pl=p,pr=p;
+    int l=(*p).second,r=(*p).first,last,plast;
+    if(p==s.begin())
+	{
+        ans-=l>>1;
+        if(l<=3)
+		{
+			ans-=r-l>>1;
+			plast=r;
+		}
+        else
+		{
+			ans-=r-l;
+			plast=r-1;
+		}
+        last=1;
+    }
+    else
+	{
+        --pl;
+        last;
+        if((*pl).second<=3)
+		{
+			last=(*pl).first;
+		}
+        else
+		{
+			last=(*pl).first-1;
+		}
+        ans-=(l-last+1)/2;
+        ans-=r-l;
+        plast=r-1;
+    }
+    ++pr;
+    if(pr==s.end())
+	{
+        return;
+    }
+    ans+=((*pr).second-last+1)>>1;
+    ans-=((*pr).second-plast+1)>>1;
+    return;
+}
+void Add(set<pair<int,int> >::iterator p)
+{
+    set<pair<int,int> >::iterator pl=p,pr=p;
+    int l=(*p).second,r=(*p).first,last,plast;
+    if(p==s.begin())
+	{
+        ans+=l>>1;
+        if(l<=3)
+		{
+			ans+=r-l>>1;
+			plast=r;
+		}
+        else
+		{
+			ans+=r-l;
+			plast=r-1;
+		}
+        last=1;
+    }
+    else
+	{
+        --pl;
+        last;
+        if((*pl).second<=3)
+		{
+			last=(*pl).first;
+		}
+        else
+		{
+			last=(*pl).first-1;
+		}
+        ans+=(l-last+1)/2;
+        ans+=r-l;
+        plast=r-1;
+    }
+    ++pr;
+    if(pr==s.end())
+	{
+        return;
+    }
+    ans-=((*pr).second-last+1)>>1;
+    ans+=((*pr).second-plast+1)>>1;
+    return;
+}
+void add(int x)
+{
+    if(!x)
+	{
+		return;
+	}
+    if(x==1)
+	{
+		x=2;
+	}
+    set<pair<int,int> >::iterator p=s.lower_bound(make_pair(x-1,-1));
+    if(p==s.end()||(*p).second>x+1)
+	{
+        int l=(1ll<<31)-1,r;
+        if(p!=s.end())
+		{
+			l=(*p).second;
+			r=(*p).first;
+		}
+        if(l==x+2)
+		{
+            Sub(p);
+            s.erase(p);
+        }
+        else
+		{
+			r=x;
+		}
+        p=s.lower_bound(make_pair(x-2,-1));
+        if(p!=s.end()&&(*p).first==x-2)
+		{
+            l=(*p).second;
+            Sub(p);
+            s.erase(p);
+        }
+        else
+		{
+			l=x;
+		}
+        s.insert(make_pair(r,l));
+		Add(s.lower_bound(make_pair(r,l)));
+        return;
+    }
+    if((*p).first==x-1)
+	{
+        int l=(*p).second;
+        Sub(p);
+        s.erase(p);
+        if(l<x-1)
+		{
+            s.insert(make_pair(x-3,l));
+			Add(s.lower_bound(make_pair(x-3,l)));
+        }
+        add(x+1);
+        return;
+    }
+    if(((*p).first-x)&1)
+	{
+        int l=(*p).second,r=(*p).first;
+        Sub(p);
+        s.erase(p);
+        if(l<x)
+		{
+            s.insert(make_pair(x-1,l));
+			Add(s.lower_bound(make_pair(x-1,l)));
+        }
+        l=r+1,r=r+1;
+        p=s.lower_bound(make_pair(r+2,-1));
+        if(p!=s.end()&&(*p).second==r+2)
+		{
+            r=(*p).first;
+            Sub(p);
+            s.erase(p);
+        }
+        s.insert(make_pair(r,l));
+		Add(s.lower_bound(make_pair(r,l)));
+        return;
+    }
+    else
+	{
+        int l=(*p).second,r=(*p).first;
+        Sub(p);
+        s.erase(p);
+        if(l<x)
+		{
+            s.insert(make_pair(x-1,l+1));
+			Add(s.lower_bound(make_pair(x-1,l+1)));
+        }
+        int nl=r+1;
+        r=r+1;
+        p=s.lower_bound(make_pair(r+2,-1));
+        if(p!=s.end()&&(*p).second==r+2)
+		{
+            r=(*p).first;
+            Sub(p);
+            s.erase(p);
+        }
+        p=s.lower_bound(make_pair(nl-2,-1));
+        if(p!=s.end()&&(*p).first==nl-2)
+		{
+            nl=(*p).second;
+            Sub(p);
+            s.erase(p);
+        }
+        s.insert(make_pair(r,nl));
+		Add(s.lower_bound(make_pair(r,nl)));
+        add(l-2);
+        return;
+    }
+}
+void del(int x)
+{
+    if(!x)
+	{
+		return;
+	}
+    if(x==1)
+	{
+		x=2;
+	}
+    set<pair<int,int> >::iterator p=s.lower_bound(make_pair(x,-1));
+    if((*p).second>x)
+	{
+        int r=(*p).first,l=(*p).second;
+        Sub(p);
+        s.erase(p);
+        if(l<r)
+		{
+			s.insert(make_pair(r,l+2));
+			Add(s.lower_bound(make_pair(r,l+2)));
+		}
+        if((x-l)&1)
+		{
+            if(l-2>=x+1)
+			{
+                p=s.lower_bound(make_pair(x-1,-1));
+                if(p==s.end()||(*p).first!=x-1)
+				{
+					s.insert(make_pair(l-2,x+1));
+					Add(s.lower_bound(make_pair(l-2,x+1)));
+				}
+                else
+				{
+                    int nl=(*p).second;
+                    Sub(p);
+                    s.erase(p);
+                    s.insert(make_pair(l-2,nl));
+					Add(s.lower_bound(make_pair(l-2,nl)));
+                }
+            }
+            add(l-2);
+        }
+        else
+		{
+            p=s.lower_bound(make_pair(x-1,-1));
+            if(p==s.end()||(*p).first!=x-1)
+			{
+				s.insert(make_pair(l-1,x+1));
+				Add(s.lower_bound(make_pair(l-1,x+1)));
+			}
+            else
+			{
+                int nl=(*p).second;
+                Sub(p);
+                s.erase(p);
+                s.insert(make_pair(l-1,nl));
+				Add(s.lower_bound(make_pair(l-1,nl)));
+            }
+        }
+        return;
+    }
+    if(((*p).second-x)&1)
+	{
+        int r=(*p).first,l=(*p).second;
+        Sub(p);
+        s.erase(p);
+        s.insert(make_pair(x-1,l));
+		Add(s.lower_bound(make_pair(x-1,l)));
+        if(x+3<=r)
+		{
+			s.insert(make_pair(r,x+3));
+			Add(s.lower_bound(make_pair(r,x+3)));
+		}
+        add(x-1);
+        return;
+    }
+    else
+	{
+        int r=(*p).first,l=(*p).second;
+        Sub(p);
+        s.erase(p);
+        if(r>x)
+		{
+			s.insert(make_pair(r,x+2));
+			Add(s.lower_bound(make_pair(r,x+2)));
+		}
+        if(l<x)
+		{
+			s.insert(make_pair(x-2,l));
+			Add(s.lower_bound(make_pair(x-2,l)));
+		}
+        return;
+    }
+}
+int X[1000],Y[1000];
+void solve()
+{
+    int a,b;
+    scanf("%d%d",&a,&b);
+    ++b;
+    int op=0,OP=0;
+    if(a<0)
+	{
+		OP=1;
+		a=-a;
+	}
+    int cnt=0,cnt2=0;
+    while(a)
+	{
+        int k=upper_bound(L+1,L+44,a)-L-1;
+        a-=L[k];
+        op=OP;
+        if(op&1)
+		{
+			Y[cnt2++]=b+k;
+		}
+        else
+		{
+			X[cnt++]=b+k;
+		}
+        if(b-k>=0)
+		{
+            op^=k&1;
+            if(op&1)
+			{
+				Y[cnt2++]=b-k;
+			}
+            else
+			{
+				X[cnt++]=b-k;
+			}
+        }
+        else
+		{
+            op^=k&1;
+            if((b-k+1)&1)
+			{
+				op^=1;
+			}
+            if(op&1)
+			{
+				Y[cnt2++]=k-b;
+			}
+            else
+			{
+				X[cnt++]=k-b;
+			}
+        }
+    }
+    int i;
+    for(i=0;i<cnt;++i)
+	{
+		add(X[i]);
+	}
+    for(i=0;i<cnt2;++i)
+	{
+		del(Y[i]);
+	}
+    printf("%lld\n",ans);
+}
+int main()
+{
+    L[0]=2;
+    L[1]=1;
+    int i;
+    for(i=2;i<44;++i)
+	{
+		L[i]=L[i-1]+L[i-2];
+	}
+    int T;
+    scanf("%d",&T);
+    while(T--)
+	{
+        ans=0;
+        s.clear();
+        int n;
+        scanf("%d",&n);
+        while(n--)
+		{
+			solve();
+		}
+    }
+}
 </code>
@@ 行 333: / 行 734: @@
 =====I=====
-<hidden>
+题目、解答与代码见[[Stirling数]]。
-<code C>
-</code>
-</hidden>
 =====K=====

CVBB ACM Team

用户工具

站点工具

差别

页面工具