ZJT's Blog

Keep your determination.

集训队作业之ARC082-F

2017-12-16 8:22017-12-16 8:2
集训队作业AtCoder二分倍增

传送门

其实就是一个数不断加加减减,并且不能超出$[0,X]$的范围。我们可以二分出在什么时刻第一次超出边界,那这之后就跟初始的$a_i$无关了。同样,对于每个时刻的$a=0$和$a=X$,我们也要预处理出这之后第一次超出边界的时刻,然后建成树之后在上面倍增跳就行了。

#include <cstdio>
#include <cstring>
#include <set>
#define LL long long
#define MAXN 200010
using namespace std;

int n,m;
LL ti[MAXN],L,d[MAXN],sd[MAXN];
int p[MAXN][2],nump;
int pre[MAXN][21];
set< pair<LL,int> > S1,S2;

int getp(LL v,LL delta){
    int t1=n+1,t2=n+1;
    set< pair<LL,int> >::iterator it=S1.lower_bound(make_pair(delta-v,0));
    if(it!=S1.begin()) t1=(--it)->second;
    it=S2.lower_bound(make_pair(L+delta-v+1,0));
    if(it!=S2.end()) t2=it->second;
    if(t1==n+1 && t2==n+1) return nump+1;
    if(t1<t2) return p[t1][0];
    else return p[t2][1];
}

void pre_gao(int x){
    while(!S1.empty() && (--S1.end())->first>=sd[x]) S1.erase(--S1.end());
    S1.insert(make_pair(sd[x],x));
    while(!S2.empty() && S2.begin()->first<=sd[x]) S2.erase(S2.begin());
    S2.insert(make_pair(sd[x],x));
    pre[p[x][0]][0]=getp(0,sd[x]);
    pre[p[x][1]][0]=getp(L,sd[x]);
}

LL calc(LL delta,LL v,LL t){
    int l=0,r=n;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(ti[mid]<=t) l=mid;
        else r=mid-1;
    }
    LL res=v+sd[l]-delta;
    if(l&1) res+=t-ti[l];
    else res-=t-ti[l];
    if(res<0) res=0;
    if(res>L) res=L;
    return res;
}

LL query(LL t,LL v){
    int temp=getp(v,0);
    if(!temp || ti[temp]>t) return calc(0,v,t);
    for(int i=20;i>=0;i--)
        if(ti[pre[temp][i]]<=t)
            temp=pre[temp][i];
    return calc(sd[(temp-1)%n+1],(temp>n)?L:0,t);
}

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%lld%d",&L,&n);
    n++;
    for(int i=1;i<=n;i++){
        if(i<n) scanf("%lld",ti+i);
        else ti[i]=ti[i-1]+L;
        d[i]=ti[i]-ti[i-1];
        if(i&1) d[i]=-d[i];
        sd[i]=sd[i-1]+d[i];
    }
    for(int i=1;i<=n;i++) p[i][0]=++nump;
    for(int i=1;i<=n;i++) ti[p[i][1]=++nump]=ti[i];
    ti[nump+1]=1LL<<60;
    for(int i=n;i>=1;i--) pre_gao(i);
    for(int j=0;j<=20;j++) pre[nump+1][j]=nump+1;
    for(int i=n;i>=1;i--){
        for(int j=1;j<=20;j++) pre[p[i][0]][j]=pre[pre[p[i][0]][j-1]][j-1];
        for(int j=1;j<=20;j++) pre[p[i][1]][j]=pre[pre[p[i][1]][j-1]][j-1];
    }
    scanf("%d",&m);
    while(m--){
        LL t,v;
        scanf("%lld%lld",&t,&v);
        if(t>ti[n]) t=ti[n];
        printf("%lld\n",query(t,v));
    }
    return 0;
}

查看详细内容

集训队作业之AGC003-E

2017-11-27 10:42017-12-16 8:3
集训队作业AtCoder二分

传送门

首先我们可以把所有$q_i$转化成递增的,然后对于每个 $q_i$,我们维护一个标记$b_i$,表示最终$1$~$q_i$这段对答案的贡献倍数。一开始$b_m=1$,其他$b_i=0$。

考虑怎么把$b_i$转移到前面的$b_j$上面去。我们可以在所有$q_j$里面二分找到最后一个小于$q_i$的(这里显然是$q_{i-1}$,不过为了前后形式统一,我们还是使用二分),记这个$q_j$为$q_k$,则我们把$b_k$加上$\lfloor\frac{q_i}{q_k}\rfloor b_i$,然后把剩下的$q_i\bmod q_k$递归下去,直到小于等于$q_1$为止。由于每次取模至少减半,所以最多会递归$O(\log q_i)$层。

经过这样逐层的转移,对于$1$到$q_i$之间的每个$i$,我们可以统计出$1$~$i$这一段对答案的贡献。对于每个数字,最终出现的次数就是这个东西的后缀和,然后就做完了,时间复杂度是$O(n\log q_i\log n)$。

话说这题以前做过,结果今天做的时候又突然想不起来之前是怎么做的了,硬是盯了几分钟才突然想起来以前的做法。。。

#include <cstdio>
#include <cstring>
#define MAXN 100010
#define LL long long

int n,m;
LL a[MAXN],b[MAXN],ans[MAXN];
LL tag[MAXN];

void input(){
    int _m;
    scanf("%d%d",&n,&_m);
    a[++m]=n;
    while(_m--){
        LL x;
        scanf("%lld",&x);
        while(m && a[m]>=x) m--;
        a[++m]=x;
    }
}

void gao(LL x,LL d){
    if(x<=a[1]){
        b[x]+=d;
        return;
    }
    int l=1,r=m;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(a[mid]<x) l=mid;
        else r=mid-1;
    }
    tag[l]+=d*(x/a[l]);
    gao(x%a[l],d);
}

int main(){
    input();
    tag[m]=1;
    for(int i=m;i>=1;i--) gao(a[i],tag[i]);
    LL s=0;
    for(int i=n;i>=1;i--) ans[i]=s+=b[i];
    for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
    return 0;
}

查看详细内容