Zip-line Codeforces - 650D || 风筝

时间:2022-11-26 11:52:42

https://codeforces.com/contest/650/problem/D


原题?

http://210.33.19.103/contest/1024/problem/2

4s 520M

Zip-line Codeforces - 650D || 风筝

Zip-line Codeforces - 650D || 风筝


题解很明白了:

Zip-line Codeforces - 650D || 风筝

当初想错了,想用stormwind的做法去做,发现要维护

给出数组a,f,g
j<i<k,a[j]<a[k]
对于每个i,求f[j]+g[k]最大值

维护了极其长的时间,啥也没维护出来。。。

错误记录:

1.第一次用lower_bound离散化,出了一些奇怪的小错误(关键是小数据根本测不出错..)

2.主席树卡空间,只好强行改成不可持久化的

Zip-line Codeforces - 650D || 风筝Zip-line Codeforces - 650D || 风筝
  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<vector>
  5 #include<set>
  6 using namespace std;
  7 #define fi first
  8 #define se second
  9 #define mp make_pair
 10 #define pb push_back
 11 typedef long long ll;
 12 typedef unsigned long long ull;
 13 typedef pair<int,int> pii;
 14 int ld,rd;
 15 namespace S
 16 {
 17 
 18 #define lc (num<<1)
 19 #define rc (num<<1|1)
 20 const int N=5000100;
 21 int maxn[N];
 22 void clr(){memset(maxn,0,sizeof(maxn));}
 23 int qmax(int L,int R,int l,int r,int num)
 24 {
 25     if(L<=l&&r<=R)    return maxn[num];
 26     int mid=l+((r-l)>>1);int ans=ld;
 27     if(L<=mid)    ans=max(ans,qmax(L,R,l,mid,lc));
 28     if(mid<R)    ans=max(ans,qmax(L,R,mid+1,r,rc));
 29     return ans;
 30 }
 31 void setmaxx(int L,int x,int l,int r,int num)
 32 {
 33     if(l==r)
 34     {
 35         maxn[num]=max(maxn[num],x);
 36         return;
 37     }
 38     int mid=l+((r-l)>>1);
 39     if(L<=mid)    setmaxx(L,x,l,mid,lc);
 40     else    setmaxx(L,x,mid+1,r,rc);
 41     maxn[num]=max(maxn[lc],maxn[rc]);
 42 }
 43 
 44 }
 45 int f[500100],g[500100];
 46 int an1[500100];
 47 int a[500100];
 48 bool onlis[500100];
 49 int n,m;
 50 int lis;
 51 int tmp[500100];
 52 struct QQ
 53 {
 54     int fi,se,n;
 55 }q[500100];
 56 bool c1(const QQ &a,const QQ &b){return a.fi<b.fi;}
 57 bool c3(const QQ &a,const QQ &b){return a.n<b.n;}
 58 int tt[1000100],t1[500100],t2[500100];
 59 int main()
 60 {
 61     int i,j;
 62     scanf("%d%d",&n,&m);
 63     //n=400000;m=400000;
 64     for(i=1;i<=n;i++)
 65     {
 66         scanf("%d",&a[i]);
 67         //a[i]=rand();
 68         tt[++tt[0]]=a[i];
 69     }
 70     for(i=1;i<=m;i++)
 71     {
 72         scanf("%d%d",&q[i].fi,&q[i].se);
 73         //q[i].fi=rand()%n+1;q[i].se=rand();
 74         q[i].n=i;
 75         tt[++tt[0]]=q[i].se;
 76     }
 77     sort(tt+1,tt+tt[0]+1);tt[0]=unique(tt+1,tt+tt[0]+1)-tt-1;
 78     for(i=1;i<=n;i++)    a[i]=lower_bound(tt+1,tt+tt[0]+1,a[i])-tt;
 79     for(i=1;i<=m;i++)    q[i].se=lower_bound(tt+1,tt+tt[0]+1,q[i].se)-tt;
 80     /*
 81     for(i=1;i<=n;i++)
 82         if(a[i]<=0||a[i]>tt[0])
 83             exit(-1);
 84     */
 85     ld=0;rd=tt[0]+1;
 86     //printf("6t%d %d\n",ld,rd);
 87     sort(q+1,q+m+1,c1);
 88     for(i=1,j=1;i<=n;i++)
 89     {
 90         //printf("1t%d %d %d %d\n",ld,a[i]-1,ld,rd);
 91         f[i]=S::qmax(ld,a[i]-1,ld,rd,1)+1;
 92         while(j<=m&&q[j].fi<=i)
 93         {
 94             t1[q[j].n]=S::qmax(ld,q[j].se-1,ld,rd,1)+1;
 95             ++j;
 96         }
 97         S::setmaxx(a[i],f[i],ld,rd,1);
 98     }
 99     S::clr();
100     for(i=n,j=m;i>=1;i--)
101     {
102         g[i]=S::qmax(a[i]+1,rd,ld,rd,1)+1;
103         while(j>0&&q[j].fi>=i)
104         {
105             t2[q[j].n]=S::qmax(q[j].se+1,rd,ld,rd,1)+1;
106             --j;
107         }
108         S::setmaxx(a[i],g[i],ld,rd,1);
109     }
110     for(i=1;i<=n;i++)
111         lis=max(lis,f[i]);
112     //for(i=1;i<=n;i++)
113     //    printf("ft%d\n",f[i]);
114     //for(i=1;i<=n;i++)
115     //    printf("gt%d\n",g[i]);
116     S::clr();
117     for(i=n;i>=1;i--)
118     {
119         onlis[i]=(S::qmax(a[i]+1,rd,ld,rd,1)+f[i])==lis;
120         if(onlis[i])
121         {
122             ++tmp[f[i]];
123             S::setmaxx(a[i],g[i],ld,rd,1);
124         }
125     }
126     for(i=1;i<=n;i++)
127         if(onlis[i]&&tmp[f[i]]==1)
128             an1[i]=lis-1;
129         else
130             an1[i]=lis;
131     sort(q+1,q+m+1,c3);
132     for(i=1;i<=m;i++)
133     {
134         //printf("1t%d %d\n",t1[i],t2[i]);
135         printf("%d\n",max(t1[i]+t2[i]-1,an1[q[i].fi]));
136     }
137     return 0;
138 }
View Code