CF809D Hitchhiking in the Baltic States
CF809D
长度为n的序列{xi},n<=3e5,范围在(li,ri)之间，求LIS最长是多长
g(i,l)表示前i个数，LIS长度为l，最后一个数最小是多少（就是那个单调栈）
g(i,l)=min(g(i-1,l),xi (if exist j g(j,l-1)<x))
关于l是递增的。
虽然不知道xi是多少，
但是可以直接用(li,ri)进行计算！最后一定存在一种方法还原xi
刚好可以把一个g(i-1,l-1)+1->g(i,l)
整个区间往上平移再往右平移，再再最下面插入一个点。
实现时候，用平衡树，直接区间+1，某位置插入一个点
最后平衡树点数即为答案
#include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') #define pb push_back #define solid const auto & #define enter cout<<endl #define pii pair<int,int> using namespace std; typedef long long ll; template<class T>il void rd(T &x){char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x); } template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Miracle{ const int N=3e5+5; int n,l[N],r[N]; int tot; struct node{int ls,rs;int ad;int val;int prio; }t[2*N]; int nc(int v){++tot;t[tot].val=v;t[tot].prio=rand();t[tot].ad=t[tot].ls=t[tot].rs=0;// cout<<" nc "<<tot<<" : "<<v<<endl;return tot; } void pushdown(int x){if(x&&t[x].ad){t[t[x].ls].ad+=t[x].ad;t[t[x].rs].ad+=t[x].ad;t[t[x].ls].val+=t[x].ad;t[t[x].rs].val+=t[x].ad;t[x].ad=0;} } void split(int now,int &x,int &y,int k){//<=kif(!now){x=0;y=0;return;}pushdown(now);if(t[now].val<=k){x=now;split(t[now].rs,t[x].rs,y,k);}else{y=now;split(t[now].ls,x,t[y].ls,k);} } int dele(int x){pushdown(x);int rt=x;if(!t[x].ls) {// cout<<" delert "<<x<<" "<<t[x].val<<endl;return t[x].rs;}int y=0;while(t[x].ls){// cout<<" ls "<<x<<" las "<<y<<endl; pushdown(x);y=x;x=t[x].ls;}// cout<<" dele "<<x<<" "<<t[x].val<<" "<<t[x].ls<<" "<<t[x].rs<<endl;t[y].ls=t[x].rs;return rt; } int merge(int x,int y){if(!x||!y) return x+y;pushdown(x);pushdown(y);if(t[x].prio<t[y].prio){t[x].rs=merge(t[x].rs,y);return x;}else{t[y].ls=merge(x,t[y].ls);return y;} } int ans=0; void fin(int x){if(!x) return ;pushdown(x);++ans;fin(t[x].ls);// cout<<" x "<<x<<" : "<<t[x].val<<endl; fin(t[x].rs); } int main(){srand(19260817);rd(n);for(reg i=1;i<=n;++i){rd(l[i]);rd(r[i]);}int rt=0;for(reg i=1;i<=n;++i){int x,y,p,q;split(rt,x,y,l[i]-1);split(y,p,q,r[i]-1);t[p].ad++;t[p].val++;// if(i==n) {// // cout<<" qqqq "<<endl;// fin(q);// }q=dele(q);// if(i==n) {// // cout<<" qqqq "<<endl;// fin(q);// }rt=merge(merge(merge(x,nc(l[i])),p),q);// cout<<"finfifn "<<i<<"------------------------"<<endl;// fin(rt); }ans=0;fin(rt);ot(ans);return 0; }} signed main(){Miracle::main();return 0; }/*Author: *Miracle* */