首页 > 其他分享 >2023NOIP A层联测32 T4 红楼 ~ Eastern Dream

2023NOIP A层联测32 T4 红楼 ~ Eastern Dream

时间:2023-11-16 16:47:58浏览次数:47  
标签:BF ch Eastern 32 T4 sqrt maxn maxm buf

2023NOIP A层联测32 T4 红楼 ~ Eastern Dream

根号分治加分块。

Ps:分块后面真的用的多。

思路

考虑根号分治,将 \(x\) 分为 \(x \leq \sqrt n\) 的情况和 \(x>\sqrt n\) 的情况。

\(x \leq \sqrt n\)

由于这一部分较小,如果在线段上暴力添加肯定会超时。

先设 \(f_{x,i}\) 表示模 \(x\) 等于 \(i\) 的数加的值,这个值可以每次暴力维护,时间 \(O(\sqrt n)\)。

再维护一个 \(f_x\) 的前缀和,也是 \(O(\sqrt n)\)。

每次查询时,枚举 \(x\),求 \([l,r]\) 中有几个 \(x\) 余数的整段。

对于整段,可以直接乘求贡献;对于区间前后的零散段,可以通过前缀和求贡献。

这一部分的维护和查询均 \(O(\sqrt n)\)。

\(x>\sqrt n\)

对于修改操作,直接去暴力跳原数列上的 \(\frac{n}{x}\) 段去区间修改,对于一段使用线段树可以达到 \(\log n\) 的效果,但是有最多 \(\sqrt n\) 段,所以说没一段必须要 \(O(1)\) 修改,而查询可以支持 \(O(\sqrt n)\)。

不难想到可以分块,对于整数段可以直接加上一个值,对于零散块可以差分。由于每一段最多访问 \(2\) 次,所以复杂度可以保证在 \(O(\sqrt n)\)。

总结一下,对于 \(x \leq \sqrt n\) 的情况,更改维护 \(f_x\) 的前缀和,查询直接暴力加查询区间的值。

对于 \(x>\sqrt n\) 的情况,使用分块维护更改,查询也直接加查询区间内的块就 OK。

时间复杂度 \(O(m\sqrt n)\)。

CODE

#include<bits/stdc++.h>
using namespace std;

#define ll long long

const int maxn=2e5+5,maxm=1000;

int n,m,block,a[maxn],L[maxn],R[maxn];

ll sum[maxm],c[maxn],pub[maxn],f[maxm][maxm],fs[maxm][maxm];
namespace IO{
    #define BF_SIZE 100000
    bool IOerr=0;
    inline char nc(){
        static char buf[BF_SIZE],*p1=buf+BF_SIZE,*pend=buf+BF_SIZE;
        if(p1==pend){
            p1=buf;
            pend=buf+fread(buf,1,BF_SIZE,stdin);
            if(pend==p1){IOerr=1;return -1;}
        }
        return *p1++;
    }
    inline bool bla(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline void Rd(int &x){
        char ch;
        while(bla(ch=nc()));
        if(IOerr){return;}
        for(x=ch-'0';(ch=nc())>='0'&&ch<='9';x=x*10+ch-'0');
    }
    inline void Rd(ll&x){
        char ch;
        while(bla(ch=nc()));
        if(IOerr){return;}
        for(x=ch-'0';(ch=nc())>='0'&&ch<='9';x=x*10+ch-'0');
    }
    #undef BF_SIZE
};
inline void write(ll X)
{
    if(X<0) {X=~(X-1); putchar('-');}
    if(X>9) write(X/10);
    putchar(X%10+'0');
}

inline void ycl()
{
    for(int i=1;i<=n;i++)
    {
        int id=(i-1)/block;
        sum[id]+=a[i];
    }
}

int main()
{
    IO::Rd(n), IO::Rd(m);
    block=max((int)sqrt(n/4),1);
    for(int i=1;i<=n;i++) IO::Rd(a[i]);
    for(int i=0;i<=(n-1)/block;i++) L[i]=block*i+1,R[i]=block*i+block;
    ycl();
    for(int o=1;o<=m;o++)
    {
        int op,x,y;
        ll k;
        IO::Rd(op);IO::Rd(x);IO::Rd(y);
        if(op==2)
        {
            int l=x,r=y;
            ll ans=0;
            for(int i=1;i<=block;i++)
            {
                int tl=(l-1)%i,tr=(r-1)%i;
                int ml=(l-1)/i,mr=(r-1)/i;
                if(ml==mr) ans+=fs[i][tr+1]-fs[i][tl];
                else
                {
                    ans+=(mr-ml-1)*fs[i][i];
                    ans+=fs[i][i]-fs[i][tl];
                    ans+=fs[i][tr+1];
                }
            }
            int idl=(l-1)/block,idr=(r-1)/block;
            if(idl==idr)
            {
                ll cj=0;
                for(int i=L[idl];i<l;i++) cj+=c[i];
                for(int i=l;i<=r;i++)
                {
                    cj+=c[i];
                    ans+=cj+pub[idl]+a[i];
                }
            }
            else
            {
                ll cj=0;
                for(int i=L[idl];i<l;i++) cj+=c[i];
                for(int i=l;i<=R[idl];i++)
                {
                    cj+=c[i];
                    ans+=cj+pub[idl]+a[i];
                }
                for(int i=idl+1;i<idr;i++) ans+=sum[i];
                cj=0;
                for(int i=L[idr];i<=r;i++)
                {
                    cj+=c[i];
                    ans+=cj+pub[idr]+a[i];
                }
            }
            write(ans);
            putchar('\n');
            continue;
        }
        IO::Rd(k);
        y=min(y,x-1);
        if(x<=block)
        {
            for(int i=1;i<=y+1;i++) f[x][i]+=k;
            for(int i=1;i<=x;i++) fs[x][i]=fs[x][i-1]+f[x][i];
        }
        else
        {
            for(int i=1;i<=n;i+=x)
            {
                int l=i,r=i+y;
                r=min(r,n);
                int idl=(l-1)/block,idr=(r-1)/block;
                if(idl==idr)
                {
                    c[l]+=k;
                    if(r<min((int)R[idl],n)) c[r+1]-=k;
                    sum[idl]+=(r-l+1)*k;
                }
                else
                {
                    c[l]+=k;
                    sum[idl]+=(R[idl]-l+1)*k;
                    for(int i=idl+1;i<idr;i++)
                    {
                        pub[i]+=k;
                        sum[i]+=k*block;
                    }
                    c[L[idr]]+=k;
                    sum[idr]+=(r-(L[idr])+1)*k;
                    if(r<min((int)R[idr],n)) c[r+1]-=k;
                }
            }
        }
    }
}

标签:BF,ch,Eastern,32,T4,sqrt,maxn,maxm,buf
From: https://www.cnblogs.com/binbinbjl/p/17836639.html

相关文章

  • C#中 (int)、int.Parse()、int.TryParse、Convert.ToInt32()四种转换的区别
    1、(int)是一种类型转换;当我们从int类型到long,float,double,decimal类型,可以使用隐式转换,但是当我们从long类型到int类型就需要使用显式转换,否则会产生编译错误。2、int.Parse()是一种类容转换;表示将数字内容的字符串转为int类型。  如果字符串为空,则抛出ArgumentNullExcept......
  • GD32F103C8T6看门狗
    GD32F10x看门狗两个看门狗设备(独立看门狗IWDG和窗口看门狗WWDG)可用来检测和解决由软件错误引起的故障;当计数器达到给定的超时值时,触发一个中断(仅适用于窗口型看门狗)或产生系统复位。一、独立看门狗IWDG特性:自由运行的递减计数器;时钟由独立的RC振荡器提供(可在停止和待机模......
  • abc327F - Apples(线段树)
    https://atcoder.jp/contests/abc327/tasks/abc327_f我们将时间看作x轴,位置看作y轴,那么我们随着时间增加,维护新加的点对区间的贡献,同时减去过时的点,线段树区间加法维护最大值即可。#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<map>#incl......
  • 2023NOIP A层联测32
    2023NOIPA层联测32目录2023NOIPA层联测32AflandreB.meirinC.sakuyaD.红楼~EasternDream总结Aflandre有\(n\)种烟花,每种烟花有两个参数\(a,b\),你要构造一种燃放顺序,使得\(b\)的和最大,\(b\)会改变,具体来说:设\(i\)在\(j\)前燃放,那么。\(a_i<a_j\),则\(b_......
  • 2023-2024-1 20231329《计算机基础与程序设计》第8周学习总结
    作业信息这个作业属于哪个课程https://edu.cnblogs.com/campus/besti/2023-2024-1-CFAP这个作业要求在哪里https://www.cnblogs.com/rocedu/p/9577842.html#WEEK08这个作业的目标计算机科学概论第9章并完成云班课测试《C语言程序设计》第7章并完成云班课测试作......
  • luoguP3287 [SCOI2014] 方伯伯的玉米田
    题目描述方伯伯在自己的农田边散步,他突然发现田里的一排玉米非常的不美。这排玉米一共有NN株,它们的高度参差不齐。方伯伯认为单调不下降序列很美,所以他决定先把一些玉米拔高,再把破坏美感的玉米拔除掉,使得剩下的玉米的高度构成一个单调不下降序列。方伯伯可以选择一个区间,把这......
  • mkfs.xfs报错 mkfs.xfs: /dev/new/new_box appears to contain an existing fil
    在设置逻辑卷文件类型时候报错mkfs.xfs:/dev/new/new_boxappearstocontainanexistingfilesystem(ext4).mkfs.xfs:Usethe-foptiontoforceoverwrite.上面是说目标分区,已经存在一个文件系统但是我们有很需要他更改文件系统的话就加一个-f选项[root@server~]......
  • 2023NOIP A层联测31 T4 民主投票
    2023NOIPA层联测31T4民主投票思维好题。思路首先可以设\(s\)每个人最多获得的票数,一开始所有点都把自己的票投给自己父亲。如果一个点的票数超过\(s\)了,那么这个点肯定要把票分给他的父亲。设\(f_{u,s}\)为\(u\)点在最多获得\(s\)票的情况下要向父亲分的票数(不......
  • RK3328-dmesg
    [0.000000]BootingLinuxonphysicalCPU0x0[0.000000]Initializingcgroupsubsyscpuset[0.000000]Initializingcgroupsubsyscpu[0.000000]Initializingcgroupsubsyscpuacct[0.000000]Linuxversion4.4.194(jenkins@jenkins-seafile......
  • AtCoder Beginner Contest(abc) 328
    B-11/11难度:⭐题目大意在某个世界一年有n个月,每个月有di天,问有多少个日期,该日期和月份组成的数字都是一样的;eg:11月的1日,22月的22日;解题思路暴力就行;神秘代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;typedefpair<int......