本文共 2348 字，大约阅读时间需要 7 分钟。
当一阵风吹来，风筝飞上天空，为了你，而祈祷，而祝福，而感动……
oyiya 在 AK 了 IOI 之后来到了乡下，在田野中玩耍，放松身心。
他发现前面有一排小朋友在放风筝，每一个风筝有一个高度 hi，风筝的高度可能会随着小朋友的心情而改变。这时，毒瘤的 oyiya 有了一个毒瘤的 idea，他想知道改变高度之后风筝的最长严格上升子序列。oyiya 太强了表示并不想做这种水题，你能解决这个问题吗？
第一行为两个整数 n, m，表示小朋友的个数和询问数。
第二行有 n 个整数，表示 hi。
接下来 m 行，每行两个整数 ai, bi，表示询问将第 ai 只风筝的高度变成 bi 后的 LIS。注意询问之间是独立的，后面的询问不受前面询问的影响.
m 行，每行一个整数表示询问的答案。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #define N 800005 7 using namespace std; 8 int c[N],a[N],cnt,d[N],Ans[N],dp[N],DP[N]; 9 int lowbit(int x){ 10 return x&(-x); 11 } 12 void add(int x,int v){ 13 while(x<=cnt){ 14 c[x]=max(c[x],v); 15 x+=lowbit(x); 16 } 17 } 18 int query(int x){ 19 int ans=0; 20 while(x){ 21 ans=max(ans,c[x]); 22 x-=lowbit(x); 23 } 24 return ans; 25 } 26 struct node{ 27 int pos,id,w; 28 }Q[N]; 29 bool cmp(const node&a,const node&b){ 30 return a.pos >n>>m; 50 for(int i=1;i<=n;i++){ 51 cin>>a[i]; 52 d[++cnt]=a[i]; 53 } 54 for(int i=1;i<=m;i++){ 55 cin>>Q[i].pos>>Q[i].w; 56 Q[i].id=i; 57 d[++cnt]=Q[i].w; 58 } 59 sort(d+1,d+cnt+1); 60 cnt=unique(d+1,d+cnt+1)-d-1; 61 for(int i=1;i<=n;i++){ 62 a[i]=lower_bound(d+1,d+cnt+1,a[i])-d; 63 } 64 for(int i=1;i<=m;i++){ 65 Q[i].w=lower_bound(d+1,d+cnt+1,Q[i].w)-d; 66 } 67 sort(Q+1,Q+m+1,cmp); 68 int head=1; 69 for(int i=1;i<=n;i++){ 70 if(Q[head].pos>i){ 71 dp[i]=query(a[i]-1)+1; 72 add(a[i],dp[i]); 73 } 74 else{ 75 while(Q[head].pos==i&&head<=m){ 76 Ans[Q[head].id]=query(Q[head].w-1); 77 head++; 78 } 79 dp[i]=query(a[i]-1)+1; 80 add(a[i],dp[i]); 81 } 82 } 83 int max0=query(cnt); 84 head=m; 85 memset(c,0,sizeof c); 86 for(int i=n;i>=1;i--){ 87 if(Q[head].pos =1){ 94 Ans[Q[head].id]+=Query(Q[head].w+1); 95 head--; 96 } 97 DP[i]=Query(a[i]+1)+1; 98 Add(a[i],DP[i]); 99 if(DP[i]+dp[i]==max0+1)check[dp[i]]++;100 }101 }102 for(int i=1;i<=m;i++){103 int nowans=0;104 if(dp[Q[i].pos]+DP[Q[i].pos]==max0+1&&check[dp[Q[i].pos]]==1)nowans=max0-1;105 else nowans=max0;106 Ans[Q[i].id]=max(Ans[Q[i].id]+1,nowans);107 }108 for(int i=1;i<=m;i++)cout< <<'\n';109 return 0;110 }
over
转载于:https://www.cnblogs.com/saionjisekai/p/9896553.html
