临时存储

26.4.3
导弹拦截

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010];
int d1[100010],d2[100010];
int main()
{while(cin>>a[++n]);n--;//n=8;//for(int i=1;i<=n;i++) cin>>a[i];int ans=0,ans2=0;for(int i=1;i<=n;i++){int t=upper_bound(d1,d1+ans,a[i],greater<int>())-d1;d1[t]=a[i];if(t==ans) ans++;int t2=lower_bound(d2,d2+ans2,a[i])-d2;d2[t2]=a[i];if(t2==ans2) ans2++;}cout<<ans<<'\n'<<ans2;return 0;
}

P7497

#include<bits/stdc++.h>
#define itn int
#define mid ((l+r)>>1)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
using namespace std;
int n,m;
const int N=200010;
const int mod=1000000007;
int la1[N*4],la2[N*4],la3[N*4];
int a[N];
queue<pair<int ,pair<int,int> > > fre;
struct segment
{int sum1,sum2,num,la1,la2,lock;
}s[N*4];
void add(int now,int l,int r,int num)
{s[now].sum1=(s[now].sum1+(r-l+1-s[now].num)*num%mod)%mod;s[now].la1=(s[now].la1+num)%mod;
}
void mul(int now,int num)
{s[now].sum1=(s[now].sum1*num)%mod;s[now].la1=(s[now].la1*num)%mod;s[now].la2=(s[now].la2*num)%mod;
}
void pushup(int now)
{s[now].sum1=s[ls(now)].sum1+s[rs(now)].sum1;s[now].sum2=s[ls(now)].sum2+s[rs(now)].sum2;s[now].num=s[ls(now)].num+s[rs(now)].num;s[now].la2=1;s[now].la1=0;
}
void pushdown(int now,int l,int r)
{if(!s[now].la1&&s[now].la2==1) return;mul(ls(now),s[now].la2);mul(rs(now),s[now].la2);s[now].la2=1;add(ls(now),l,mid,s[now].la1);add(rs(now),mid+1,r,s[now].la2);s[now].la1=0;
}
void build(int now,int l,int r)
{if(l==r) {s[now].sum1=a[l];return ;}build(ls(now),l,mid);build(rs(now),mid+1,r);pushup(now);
}
void update(int now,int l,int r,itn L,int R,int num,int opt)
{if(r<L||R<l) return;if(L<=l&&r<=R) {if(opt==1) add(now,l,r,num);else mul(now,num); return;}pushdown(now,l,r);update(ls(now),l,mid,L,R,num,opt);update(rs(now),mid+1,r,L,R,num,opt);pushup(now); 
}
void freeze(int now,int l,int r,int L,int R)
{if(r<L||R<l) return;if(L<=l&&r<=R){s[now].lock++;s[now].sum2+=s[now].sum1;s[now].sum1=0;}
}
int ask(int now,int l,int r,int L,int R)
{if(r<L||R<l) return 0;if(L<=l&&r<=R) return s[now].sum1+s[now].sum2;pushdown(now,l,r);return ask(ls(now),l,mid,L,R)+ask(rs(mow),mid+1,r,L,R);
}
int main()
{	int n,m;cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];build(1,1,n);for(int i=1;i<=m;i++){int opt,l,r,x;cin>>opt>>l>>r;if(opt==4) cout<<ask(1,1,n,l,r)<<'\n';else if(opt==3){cin>>x;fre.emplace(x,l,r);}else {cin>>x;update(1,1,n,l,r,x,opt);}}return 0;
}