考试时的记录(t1)
//12 14 18 //13 15 17 18锅 //二分套二分不可行 //1 3 5 7 9 //2 4 6 8 10 //倍增/分块会被卡 //主席树需要带修改 //线段树根本维护不了 //set需要得知序列 //可持久化set? //莫队复杂度不对n^(5/3) //分块维护不了
觉得t1根本没法搞,主要是二分套二分被我否决了
本来打了个二分套二分,然后一拍就挂
后来就调,觉得很恶心
最后发现我二分套二分玮了
我二分策略是二分第一段长度,然后在第二段里lower_bound,upper_bound找到<第一段二分位置的值的第一位置,和>第一段二分位置值最后一个位置???
帏的
12 14 18
13 15 17 18
里15是mid我查不到
其实暴力可以直接二分答案,然后在两段里--upper_bound找到<=的值,
我这不是弱智吗
简单题复杂化,能力max
中间值
题解
$n*{log}^2$就是上面说的直接二分答案,两段里--upper_bound找到<=的值
优化成$n*log$就是二分第一段位置,找到第二段对应位置(莫名和考试时苇掉的思路相似)
看是否符合,如果二分地一段找到一个x,对应第二段位置y,符合a[x]>=b[y-1]&&a[x]<=b[r+1]就是满足条件的
代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define A 1111111 ll n,m; ll a[A],b[A]; //ll read(){ll x;cin>>x;return x;} ll read(){ ll x=0,f=1;char c=getchar(); while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();} return x*f; } ll jud(ll x,ll l,ll r){ if(x>r) return n+1; if(x<l) return 0; return x; } ll erf1(ll l1,ll r1,ll l2,ll r2){ ll len=(r2-l2+1+r1-l1+1+1)/2; ll l=l1,r=min(r1,l1+len-1); while(l<=r){ ll mid=(l+r)>>1; if(b[jud(l2+len+l1-mid-2,l2,r2)]<=a[mid]&&b[jud(l2+len-(mid-l1+1),l2,r2)]>=a[mid]) {printf("%lld ",a[mid]);return 1;} if(b[jud(l2+len+l1-mid-2,l2,r2)]>a[mid]) l=mid+1; else r=mid-1; } return 0; } ll erf2(ll l1,ll r1,ll l2,ll r2){ ll len=(r2-l2+1+r1-l1+1+1)/2; ll l=l2,r=min(r2,l2+len-1); while(l<=r){ ll mid=(l+r)>>1; if(a[jud(l2+len+l1-mid-2,l1,r1)]<=b[mid]&&a[jud(l2+len-(mid-l1+1),l1,r1)]>=b[mid]) {printf("%lld ",b[mid]);return 1;} if(a[jud(l2+len+l1-mid-2,l1,r1)]>b[mid]) l=mid+1; else r=mid-1; } return 0; } int main(){ freopen("median.in","r",stdin); freopen("median.out","w",stdout); n=read(),m=read(); for(ll i=1;i<=n;i++) a[i]=read(); for(ll i=1;i<=n;i++) b[i]=read(); a[n+1]=b[n+1]=123456798101112; for(ll i=1;i<=m;i++){ ll opt=read(); if(opt==1){ ll x=read(),y=read(),z=read(); if(x==0) a[y]=z; else b[y]=z; } else { ll l1=read(),r1=read(),l2=read(),r2=read(); if(!erf1(l1,r1,l2,r2)) erf2(l1,r1,l2,r2); } } }
最小值
题解
水掉没脸,
代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define $ 1111111 ll read(){ ll x=0,f=1;char c=getchar(); while(!isdigit(c)) { if(c=='-') f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();} return x*f; } ll A,B,C,D,n; ll a[$],f[$]; //627982878638142 //min满足单调性但这个函数不一定满足 int main(){ freopen("min.in","r",stdin); freopen("min.out","w",stdout); n=read(),A=read(),B=read(),C=read(),D=read(); for(ll i=1;i<=n;i++){ a[i]=read(); } memset(f,-0x7f,sizeof(f)); f[0]=0; for(ll i=1;i<=n;i++){ ll minn=a[i]; for(ll j=i-1;j>=max(0ll,i-500);j--){ minn=min(a[j+1],minn); f[i]=max(f[i],f[j]+minn*minn*minn*A+minn*minn*B+minn*C+D); // printf("minn*minn*minn*A+minn*minn*B+minn*C+D=%lld ",minn*minn*minn*A+minn*minn*B+minn*C+D); // if(minn*minn*minn*A+minn*minn*B+minn*C+D<0) break; } } printf("%lld ",f[n]); }