translate
Trees can be planted at the position of 1 ∼ n1 ∼ n1 ∼ n, and can be planted at the beginning.
There will be operations in the third moment:
1. PIP ﹣ IPI ﹣ a tree with a height of HIH ﹣ IHI ﹣ is planted in a position where no tree has been planted.
2. Cut down the first tree to ensure that no trees will be planted at this location in the future.
Every day the trees grow 111
Output the longest ascending subsequence length for each operation
Tree height is different at any time
Problem solving
After reading the questions Can not do
After reading the data range Have some ideas
The height of each entry will not exceed 10
No more than the top ten trees will be deleted at a time
Make sure that no tree is the same height at any time
A dp[i]dp[i]dp[i] DP [i] is recorded at each point to indicate LIS starting with him
Obviously, adding a tree will only affect the answers of up to 10 trees
Deleting a tree will only affect the answers of up to 10 trees
For joining, you open a line tree, throw in the tree with height > 10, and take the position as the subscript
For deletion, open another line segment tree, throw in the tree with position > 10, with height as the subscript
Maximum supported
Make a mess of
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<vector> #include<ctime> #include<map> #define LL long long #define mp(x,y) make_pair(x,y) #define lc now<<1 #define rc now<<1|1 using namespace std; inline LL read() { LL f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void write(int x) { if(x<0)putchar('-'),x=-x; if(x>9)write(x/10); putchar(x%10+'0'); } inline void pr1(int x){write(x);printf(" ");} inline void pr2(int x){write(x);puts("");} int tim; struct ph { int h,x; ph(){} ph(int _h,int _x){h=_h;x=_x;} }w[200100];int v[200100]; bool cmp1(ph n1,ph n2){return n1.h<n2.h;} bool cmp2(ph n1,ph n2){return n1.x<n2.x;} ph li[200100];int pos; int s[200100],f[200100],ln; int lowbit(int x){return x&-x;} void chpos(int x,int c){for(x;x<=200000;x+=lowbit(x))s[x]+=c;} int findKth(int K) { int now=0,sum=0; for(int i=18;i>=0;i--) if(now+(1<<i)<=200000&&sum+s[now+(1<<i)]<K)sum+=s[now+(1<<i)],now+=(1<<i); return now+1; } int mx[2][410000*4]; void modify(int now,int l,int r,int p,int c,int op) { if(l==r){mx[op][now]=c;return ;} int mid=(l+r)/2; if(p<=mid)modify(lc,l,mid,p,c,op); else modify(rc,mid+1,r,p,c,op); mx[op][now]=max(mx[op][lc],mx[op][rc]); } int query(int now,int l,int r,int ql,int qr,int op) { if(ql>qr)return 0; if(l==ql&&r==qr)return mx[op][now]; int mid=(l+r)/2; if(qr<=mid)return query(lc,l,mid,ql,qr,op); else if(mid+1<=ql)return query(rc,mid+1,r,ql,qr,op); else { int t1=query(lc,l,mid,ql,mid,op); int t2=query(rc,mid+1,r,mid+1,qr,op); return max(t1,t2); } } int n,m; int ans; //The first one with position as subscript height > 10 is thrown in //The second position with height as subscript > 10 int a[200100]; int main() { // freopen("a.in","r",stdin); // freopen("a.out","w",stdout); n=read();m=read(); for(int tt=1;tt<=m;tt++) { int opt=read(),p=read(); int nw=0;sort(li+1,li+1+pos,cmp1); for(int i=1;i<=pos;i++)if(li[i].h+tt<=10)li[++nw]=li[i]; pos=nw; if(opt==1) { int h=read();a[p]=h-tt+m;chpos(p,1); for(int i=1;i<=pos;i++)if(li[i].h+tt<h)modify(1,1,n,li[i].x,0,0),modify(1,1,n+m,li[i].h+m,0,1); int hh=query(1,1,n,p,n,0)+1; modify(1,1,n,p,hh,0);modify(1,1,n+m,h-tt+m,hh,1); sort(li+1,li+1+pos,cmp1); for(int i=pos;i>=1;i--)if(li[i].h+tt<h) { hh=query(1,1,n,li[i].x+1,n,0)+1; modify(1,1,n,li[i].x,hh,0);modify(1,1,n+m,li[i].h+m,hh,1); }li[++pos]=ph(h-tt,p); } else { for(int i=1;i<=p;i++) { int u=findKth(i); modify(1,1,n,u,0,0);modify(1,1,n+m,a[u],0,1); } int nw=0,u=findKth(p);a[u]=0;chpos(u,-1); for(int i=1;i<=pos;i++)if(li[i].x!=u)li[++nw]=li[i]; pos=nw; for(int i=p-1;i>=1;i--) { u=findKth(i);int hh=query(1,1,n+m,a[u],n+m,1)+1; modify(1,1,n,u,hh,0);modify(1,1,n+m,a[u],hh,1); } } pr2(mx[0][1]); } return 0; }