题解 P3747 【[六省联考2017]相逢是问候】

2019-07-29 23:11:31


看到这题题解都是什么线段树维护区间最小修改次数,我来发一波并查集+树状数组的做法。

因为每个数最多被修改$O(\log P)$次,所以对于修改次数达到$\log P$的,我们可以直接跳过这一个点。考虑一个暴力,每次修改从$l$到$r$枚举每个点,这样是$O(n^2)$的,但是我们如果能够在每个点$i$处修改完之后直接跳到下一个修改次数未达到上界的点,这样复杂度就是正确的。

考虑一个与BZOJ2054类似的思路,使用并查集来支持这个操作。初始时整个序列每个位置的父亲赋为本身,对于每个修改次数达到上界的点$i$,我们将$i$并到$i+1$上。那么点$i$的下一个未达到上界的点就是$i+1$所在联通块的根(这里一定要注意合并的有序性,要把左边往右边合并)

至于区间求和,树状数组即可。

但是由于本题时间复杂度瓶颈不在于数据结构,所以这对时间的优化可能并没有太大意义……但是至少好写了一些吧

附我的AC代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#define llong long long
using namespace std;

inline int read()
{
    int x=0; bool f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
    for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
    if(f) return x;
    return -x;
}

const int N = 5e4;
const int B = 20000;
llong a[N+3];
llong b[N+3];
llong p[57];
int pos[N+3];
llong bit[N+3];
int uf[N+3];
llong pw[2][B+3][57];
int pwf[2][B+3][57];
int n,q,m; llong c;
bool flag;

llong quickpow(llong x,llong y,int mod)
{
    int y0 = y%B,y1 = y/B; llong ret = pw[0][y0][mod]*pw[1][y1][mod];
    flag |= pwf[0][y0][mod]|pwf[1][y1][mod]|(ret>=p[mod]);
    return ret%p[mod];
}

llong getphi(llong x)
{
    llong ret = x; int i = 2;
    while(i*i<=x && x>1)
    {
        if(x%i==0)
        {
            ret = ret/i*(i-1);
            while(x%i==0) {x/=i;}
        }
        i++;
    }
    if(x>1) {ret = ret/x*(x-1);}
    return ret;
}

int findfa(int u)
{
    int i = u;
    while(uf[u]!=u) {u = uf[u];}
    while(uf[i]!=u)
    {
        int j = uf[i]; uf[i] = u; i = j;
    }
    return u;
}

void addval(int u,llong x)
{
    while(u<=n)
    {
        bit[u] = (bit[u]+x)%p[0];
        u+=(u&(-u));
    }
}

llong querysum(int rb)
{
    llong ret = 0ll;
    while(rb)
    {
        ret = (ret+bit[rb])%p[0];
        rb -= (rb&(-rb));
    }
    return ret;
}

llong getval(int y,llong x)
{
    llong ret = x;
    flag = ret>=p[y]?true:false; ret%=p[y]; if(flag) ret+=p[y];
    for(int i=y-1; i>=0; i--)
    {
        ret = quickpow(c,ret,i);
        if(flag) ret+=p[i];
    }
    return ret%p[0];
}

int main()
{
    scanf("%d%d%lld%lld",&n,&q,&p[0],&c);
    while(p[m]!=1) {m++; p[m] = getphi(p[m-1]);} m++; p[m] = 1;
    for(int i=1; i<=n; i++) {scanf("%lld",&a[i]); a[i] %= p[0]; b[i] = a[i]; addval(i,a[i]); uf[i] = i;} uf[n+1] = n+1;
    for(int i=0; i<=m; i++)
    {
        pw[0][0][i] = 1ll;
        for(int j=1; j<=B; j++)
        {
            pw[0][j][i] = pw[0][j-1][i]*c;
            pwf[0][j][i] = pwf[0][j-1][i]|(pw[0][j][i]>=p[i]);
            pw[0][j][i] %= p[i];
        }
        pw[1][0][i] = 1ll;
        for(int j=1; j<=B; j++)
        {
            pw[1][j][i] = pw[1][j-1][i]*pw[0][B][i];
            pwf[1][j][i] = pwf[1][j-1][i]|pwf[0][B][i]|(pw[1][j][i]>=p[i]);
            pw[1][j][i] %= p[i];
        }
    }
    while(q--)
    {
        int opt,lb,rb; scanf("%d%d%d",&opt,&lb,&rb);
        if(opt==0)
        {
            for(int i=findfa(lb); i<=rb; i=findfa(i+1))
            {
                pos[i]++;
                addval(i,p[0]-b[i]);
                b[i] = getval(pos[i],a[i]);
                addval(i,b[i]);
                if(pos[i]==m) {uf[i] = i+1;}
            }
        }
        else if(opt==1)
        {
            llong ans = (querysum(rb)-querysum(lb-1)+p[0])%p[0];
            printf("%lld\n",ans);
        }
    }
    return 0;
}