Loj#2529.「ZJOI2018」胖 | wzf2000's blog

Loj#2529.「ZJOI2018」胖

Loj#2529.「ZJOI2018」胖 题解

题意:

  • 大概就是求某算法的更新次数。

题解:

  • 发现加入图片新方法!(炮姐镇楼)

railgun

  • 好了,进入正题。
  • 我们发现每条边的贡献必定是一个区间。
  • 于是二分左右端点,就是查询一个区间是否可行,端点特判即可。
  • 然后就时间复杂度 $O(n\log^2n)$ 了。

代码:

#include <bits/stdc++.h>
#define gc getchar()
#define root 1,1,n
#define lc cur<<1
#define rc lc|1
#define lson lc,l,mid
#define rson rc,mid+1,r
using namespace std;
typedef long long ll;
const int N=200009;
int n,m,a[N],vis[N];
ll sum[N],len[N],Min[2][N<<2];
ll Ans;
int read()
{
    int x=1;
    char ch;
    while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
    int s=ch-'0';
    while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
    return s*x;
}
void build(int cur,int l,int r)
{
    Min[0][cur]=Min[1][cur]=(ll)1e18;
    if (l==r) return;
    int mid=(l+r>>1);
    build(lson),build(rson);
}
void ins(int cur,int l,int r,int x,ll y,ll z)
{
    if (l==r)
    {
        Min[0][cur]=y,Min[1][cur]=z;
        return;
    }
    int mid=(l+r>>1);
    if (x<=mid) ins(lson,x,y,z);
    else ins(rson,x,y,z);
    Min[0][cur]=min(Min[0][lc],Min[0][rc]);
    Min[1][cur]=min(Min[1][lc],Min[1][rc]);
}
void qry(int cur,int l,int r,int L,int R,int k)
{
    if (L>R) return;
    if (L<=l&&R>=r)
    {
        Ans=min(Ans,Min[k][cur]);
        return;
    }
    int mid=(l+r>>1);
    if (L<=mid) qry(lson,L,R,k);
    if (R>mid) qry(rson,L,R,k);
}
void clear(int cur,int l,int r,int x)
{
    Min[0][cur]=Min[1][cur]=(ll)1e18;
    if (l==r) return;
    int mid=(l+r>>1);
    if (x<=mid) clear(lson,x);
    else clear(rson,x);
}
bool check1(int id,int pos)
{
    if (a[id]==pos) return 1;
    int L=max(1,2*pos-a[id]),R=a[id]-1;
    Ans=(ll)1e18,qry(root,L,pos,0);
    ll ret1=Ans;
    if (ret1+sum[pos]<=sum[a[id]]-sum[pos]+len[id]) return 0;
    Ans=(ll)1e18,qry(root,pos,R,1);
    ll ret2=Ans;
    if (ret2-sum[pos]<=sum[a[id]]-sum[pos]+len[id]) return 0;
    return 1;
}
bool check2(int id,int pos)
{
    if (a[id]==pos) return 1;
    int R=min(n,2*pos-a[id]-1),L=a[id]+1;
    Ans=(ll)1e18,qry(root,L,pos,0);
    ll ret1=Ans;
    if (ret1+sum[pos]<=sum[pos]-sum[a[id]]+len[id]) return 0;
    Ans=(ll)1e18,qry(root,pos,R,1);
    ll ret2=Ans;
    if (ret2-sum[pos]<=sum[pos]-sum[a[id]]+len[id]) return 0;
    if (2*pos-a[id]>n||!vis[2*pos-a[id]]) return 1;
    ll ret=len[vis[2*pos-a[id]]]+sum[2*pos-a[id]];
    if (ret-sum[pos]<sum[pos]-sum[a[id]]+len[id]) return 0;
    return 1;
}
int main()
{
    int ttt=clock();
    n=read(),m=read();
    for (int i=2;i<=n;i++) sum[i]=sum[i-1]+read();
    build(root);
    while (m--)
    {
        int K=read();
        for (int i=1;i<=K;i++)
        {
            a[i]=read(),len[i]=read();
            vis[a[i]]=i;
            ins(root,a[i],len[i]-sum[a[i]],len[i]+sum[a[i]]);
        }
        ll ret=0;
        for (int i=1;i<=K;i++)
        {
            int l=1,r=a[i],ret1,ret2;
            while (l<=r)
            {
                int mid=(l+r>>1);
                if (check1(i,mid)) ret1=mid,r=mid-1;
                else l=mid+1;
            }
            l=a[i],r=n;
            while (l<=r)
            {
                int mid=(l+r>>1);
                if (check2(i,mid)) ret2=mid,l=mid+1;
                else r=mid-1;
            }
            ret+=(ll)ret2-ret1+1;
        }
        for (int i=1;i<=K;i++) clear(root,a[i]),vis[a[i]]=0;
        printf("%lld\n",ret);
    }
    cerr<<clock()-ttt<<endl;
    return 0;
}

吐槽:

  • 考场上没看出是道斯波题,还转化错了,浪费大量时间。
  • 小猫标算 $\rm TLE$ 了 $2$ 个点,然后嘲讽了一波。
  • 然后我第一发比他还慢。
  • emmmm。。。