自动搬运

查看原文

来自洛谷，原作者为

	D0000 ClistCheckCodewKtJuzrw0q

搬运于2025-08-24 23:07:01，当前版本为作者最后更新于2024-12-14 18:46:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

可以说真的是一道不错的题。

我的做法是“分块”。

由于 $n^2$ 以上做法太简单，就不写了，直接从 $O(n\sqrt n)$ 开始。

$O((n+m+\sum k)\sqrt n)$ 做法

会的可以直接跳过。

这其实就是静态区间众数。主要思路是将原序列分成 $k$ 块，我们维护每个数在前 $i$ 个块中出现的次数，进而维护前 $i$ 个块的众数。

构建时，考虑到前 $i+1$ 个块的众数必然为前 $i$ 个块的众数，或者第 $i$ 个块中出现过的数，共 $O(\sqrt n)$ 个不同的值。

修改时，只需要修改后面的块。

注意，修改和构建时维护的所有信息只需要每个块的。

查询时类似，这里只需要查前 $i$ 个块带上不超过 $O(\sqrt n)$ 个零散的元素。

这里的 $\sum k\le 5\times 10^7$，显然就是查询次数，但是 $k\sqrt n$ 显然会超时，需要把它优化掉。

$O(\sum k+(n+m)\sqrt n)$ 做法

在查询的时候，由于右端点是一段区间，显然一个块中的答案可以在块长的时间内求出来。

但是这样仍然会超时。

$O(\sum k+(n+m)\log n)$ 做法

增加块长时修改操作会变快，但是查询中浪费的就会变多。但是又因为查询是最右边一段连续的区间。因此可以将块长设置得不一样，具体地，如果从右往左块长依次为 $1,2,4,8,\cdots$，则总共只有 $\log n$ 个块。又不妨假设所有询问答案都是 $k_0$，则总共需要查询不超过 $\frac{\sum k}{k_0}$ 次，且每次浪费的询问也不会超过 $2^{\log k_0}=k_0$ 个，总共查询复杂度即为 $O(\sum k)$。

代码

#include<cstdio>
#include<utility>
#include<algorithm>
#include<math.h>
#define int long long
int t,n,m,b[400005];
int a[400005];
long long d[400005][19];
long long app[400005];
std::pair<long long,int>zhong[400000],ans[400005];
int kuail[19],kuair[19],kuainum=19;
void run(){
    long long q;
    scanf("%lld",&q);
    for(int i=kuainum-1;~i;i--){
        ans[kuair[i-1]]=zhong[i-1];
        for(int j=kuail[i];j<=kuair[i];j++)app[b[j]]=d[b[j]][i-1];
        for(int j=kuail[i];j<=kuair[i];j++){
            ans[j]=ans[j-1];
            app[b[j]]+=a[j];
            if(app[b[j]]>ans[j].first||(app[b[j]]==ans[j].first&&b[j]>ans[j].second))ans[j]={app[b[j]],b[j]};
        }
        for(int j=kuail[i];j<=kuair[i];j++)app[b[j]]=0;
        for(int j=kuair[i];j>=kuail[i];j--){
            q^=(1ll*a[j]*ans[j].second);
            if(!q){
			printf("%lld\n",n-j+1);
			return;
			}
        }
    }
}
signed main(){
    scanf("%lld%lld%lld",&t,&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]);
    kuainum=log2(n);
    for(int i=kuainum-1;~i;i--){
        if(kuainum==i+1)kuair[i]=n;
        else kuair[i]=kuail[i+1]-1;
        if(!i)kuail[i]=1;
        else kuail[i]=kuair[i]-(1<<(kuainum-i-1));
    }
    for(int i=0;i<kuainum;i++){
        for(int j=1;j<=n;j++)d[j][i]=d[j][i-1];
        for(int j=kuail[i];j<=kuair[i];j++)d[b[j]][i]+=a[j];
        zhong[i]=zhong[i-1];
        for(int j=kuail[i];j<=kuair[i]&&j<=n;j++)if(d[b[j]][i]>zhong[i].first||(d[b[j]][i]==zhong[i].first&&b[j]>zhong[i].second))zhong[i]={d[b[j]][i],b[j]};
    }
    while(m--){
        int op,x,y;
        scanf("%lld",&op);
        if(op==2)run();
        else{
            scanf("%lld%lld",&x,&y);
            a[x]+=y;
            for(int i=0;i<kuainum;i++){
                if(kuair[i]>=x)d[b[x]][i]+=y;
                if(d[b[x]][i]>zhong[i].first||(d[b[x]][i]==zhong[i].first&&b[x]>zhong[i].second))zhong[i]={d[b[x]][i],b[x]};
            }
        }
    }
}