自动刷题机
\(solution\)
二分答案找最大最小值
考试时二分写错了
AC Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read()
{
ll x=0,f=1;
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;
}
const int N=1e5+5;
ll n,k,a[N];
ll check(ll x)
{
int cnt=0;
ll sum=0;
for(int i=1;i<=n;++i){
sum=max(0ll,sum+a[i]);
if(sum>=x){
++cnt;
sum=0;
}
}
return cnt;
}
ll ans1=-1,ans2=-1;
void get_max()
{
ll l=1,r=1e18;
while(l<=r){
ll mid=(l+r)>>1;
if(check(mid)>=k){
if(check(mid)==k)ans2=mid;
l=mid+1;
}
else if(check(mid)<k)
r=mid-1;
}
return ;
}
void get_min()
{
ll l=1,r=1e14;
while(l<=r){
ll mid=(l+r)>>1;
if(check(mid)>k)
l=mid+1;
else if(check(mid)<=k){
r=mid-1;
if(check(mid)==k)ans1=mid;
}
}
return ;
}
int main()
{
// freopen("autoac.in","r",stdin);
// freopen("autoac.out","w",stdout);
n=read(),k=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
}
get_min();
get_max();
if(ans1==-1)printf("-1\n");
else printf("%lld %lld\n",ans1,ans2);
return 0;
}
生日聚会
随机序列
\(solution\)
找规律后，线段树维护
规律\(3^{n-1}*2*suma_1+3^{n-2}*2*suma_2+\cdots +3^0*2*suma_{n-1}+suma_n\),其中\(suma_i=\sum_{j=1}^{i}{a_j}\);
AC Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read()
{
ll x=0,f=1;
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;
}
const int mod=1e9+7;
const int N=1e5+5;
ll n,q,a[N];
ll dat[N];
//ll sum[N],dat[N],ans[N];
ll qow(ll x,ll y)
{
ll res=1;
while(y>0)
{
if(y&1)
{
res*=x;res%=mod;
}
x*=x;x%=mod;y>>=1;
}
return res%mod;
}
struct ww{
int l,r;
ll sum,tag=1;
}tr[N<<3];
void updat(int p)
{
tr[p].sum=(tr[p<<1].sum%mod+tr[p<<1|1].sum%mod)%mod;
}
void build(int p,int l,int r)
{
tr[p].l=l,tr[p].r=r;
if(l==r)
{
tr[p].sum=dat[l]%mod;
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
updat(p);
}
void pushdown(int p)
{
if(tr[p].tag!=1)
{
tr[p<<1].sum=(tr[p<<1].sum*tr[p].tag)%mod;
tr[p<<1|1].sum=(tr[p<<1|1].sum*tr[p].tag)%mod;
tr[p<<1].tag=(tr[p<<1].tag*tr[p].tag)%mod;
tr[p<<1|1].tag=(tr[p<<1|1].tag*tr[p].tag)%mod;
tr[p].tag=1;
}
}
void change(int p,int l1,int r1,ll x)
{
int l=tr[p].l,r=tr[p].r;
if(r<l1||r1<l)return ;
if(l1<=l&&r<=r1)
{
pushdown(p);
tr[p].tag=(tr[p].tag*x)%mod;
tr[p].sum=(tr[p].sum*tr[p].tag)%mod;
return ;
}
pushdown(p);
int mid=(l+r)>>1;
if(l1<=mid)change(p<<1,l1,r1,x);
if(r1>mid)change(p<<1|1,l1,r1,x);
updat(p);
}
int main()
{
n=read(),q=read();
dat[n]=1;ll k=1;
for(int i=n-1;i>=1;i--)
{
dat[i]=k*2%mod;
k*=3;k%=mod;
}
// sum[0]=1;
ll sum1=1;
for(int i=1;i<=n;i++)
{
a[i]=read();
sum1=sum1*a[i]%mod;
dat[i]=sum1*dat[i]%mod;
// sum[i]=sum[i-1]*a[i]%mod;
// ans[i]=(dat[i]*sum[i]%mod+ans[i-1])%mod;
}
build(1,1,n);
ll x,y;
for(int i=1;i<=q;i++)
{
x=read(),y=read();
ll tmp=qow(a[x],mod-2)%mod*y%mod;
change(1,x,n,tmp);
a[x]=y;
printf("%lld\n",tr[1].sum%mod);
// ll tmp=qow(a[x],mod-2);
// for(int j=x;j<=n;j++)
// {
// sum[j]=sum[j]*tmp%mod*y%mod;
// ans[j]=(dat[j]*sum[j]%mod+ans[j-1])%mod;
// }
// a[x]=y;
// printf("%lld\n",ans[n]);
}
return 0;
}