LOJ #6281. 数列分块入门 5

\(\color{#0066ff}{题目描述}\)

给出一个长为 n 的数列 \(a_1\ldots a_n\) ，以及 n 个操作，操作涉及区间开方，区间求和。

\(\color{#0066ff}{输入格式}\)

第一行输入一个数字 n。

第二行输入 n 个数字，第 i 个数字为 \(a_i\) ，以空格隔开。

接下来输入 n 行询问，每行输入四个数字 \(\mathrm{opt}, l, r, c\)，以空格隔开。

若 \(\mathrm{opt} = 0\)，表示将位于 \([l,r]\) 的之间的数字都开方。对于区间中每个 \(a_i(l\le i\le r),a_i ← \lfloor \sqrt{a_i}\rfloor\)

若 \(\mathrm{opt} = 1\)，表示询问位于 \([l,r]\) 的所有数字的和。

\(\color{#0066ff}{输出格式}\)

对于每次询问，输出一行一个数字表示答案。

\(\color{#0066ff}{输入样例}\)

4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4

\(\color{#0066ff}{输出样例}\)

6
2

\(\color{#0066ff}{数据范围与提示}\)

对于 100% 的数据， \(1 \leq n \leq 50000, -2^{31} \leq \mathrm{others},\mathrm{ans} \leq 2^{31}-1\)。

\(\color{#0066ff}{题解}\)

可以用计算器算一下，\(2^{31}\)，最多开5次根号就变成1了

而\(\sqrt{1}=1,\sqrt{0}=0\),开方操作相当于没有

所以，每个块维护一个tag，当且仅当本块只有0/1时，打上标记

在区间开方的时候，对于没有打标记的块，直接暴力开方

打了标记的块，直接continue

每次开方后判断是否该打标记

对于区间和，每个块直接维护就行了

#include<cstdio>
#include<queue>
#include<vector>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
#define _ 0
#define LL long long
#define Space putchar(' ')
#define Enter putchar('\n')
#define fuu(x,y,z) for(int x=(y),x##end=z;x<=x##end;x++)
#define fu(x,y,z)  for(int x=(y),x##end=z;x<x##end;x++)
#define fdd(x,y,z) for(int x=(y),x##end=z;x>=x##end;x--)
#define fd(x,y,z)  for(int x=(y),x##end=z;x>x##end;x--)
#define mem(x,y)   memset(x,y,sizeof(x))
#ifndef olinr
inline char getc()
{
    static char buf[100001],*p1=buf,*p2=buf;
    return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100001,stdin),p1==p2)? EOF:*p1++;
}
#else
#define getc() getchar()
#endif
template<typename T>inline void in(T &x)
{
    int f=1; char ch; x=0;
    while(!isdigit(ch=getc()))(ch=='-')&&(f=-f);
    while(isdigit(ch)) x=x*10+(ch^48),ch=getc();
    x*=f;
}
const int inf=0x7fffffff;
struct K
{
    int l,r,val;
    bool tag;
    K() {l=inf,r=-inf;}
}e[50505];
struct seq
{
    int val,bel;
}a[50500];
int n,num;
inline void init()
{
    num=std::sqrt(n);
    fuu(i,1,n)
    {
        in(a[i].val),a[i].bel=(i-1)/num+1;
        e[a[i].bel].l=std::min(e[a[i].bel].l,i);
        e[a[i].bel].r=std::max(e[a[i].bel].r,i);
        e[a[i].bel].val+=a[i].val;
    }
}
inline void sqr(int l,int r)
{
    fuu(i,a[l].bel+1,a[r].bel-1) 
    {
        if(e[i].tag) continue;
        int max=0;
        fuu(j,e[i].l,e[i].r)
        {
            e[i].val-=a[j].val;
            a[j].val=std::sqrt(a[j].val);
            e[i].val+=a[j].val;
            max=std::max(max,a[j].val);
        } 
        if(max<=1) e[i].tag=true; 
    }
    fuu(i,l,std::min(r,e[a[l].bel].r))
    {
        e[a[i].bel].val-=a[i].val;
        a[i].val=std::sqrt(a[i].val);
        e[a[i].bel].val+=a[i].val;
    }
    fuu(i,e[a[l].bel].l,e[a[l].bel].r) if(a[i].val>1) goto fuck1;
    e[a[l].bel].tag=true;
    fuck1:;
    if(a[l].bel!=a[r].bel)
    {
        fuu(i,std::max(l,e[a[r].bel].l),r)
        {
            e[a[i].bel].val-=a[i].val;
            a[i].val=std::sqrt(a[i].val);
            e[a[i].bel].val+=a[i].val;
        }
        fuu(i,e[a[r].bel].l,e[a[r].bel].r) if(a[i].val>1) return;
        e[a[r].bel].tag=true;
    }
}
inline int query(int l,int r)
{
    int ans=0;
    fuu(i,a[l].bel+1,a[r].bel-1) ans+=e[i].val;
    fuu(i,l,std::min(r,e[a[l].bel].r)) ans+=a[i].val;
    if(a[l].bel!=a[r].bel) fuu(i,std::max(l,e[a[r].bel].l),r) ans+=a[i].val;
    return ans;
}
int main()
{
    in(n);
    init();
    int p,l,r,c;
    while(n--)
    {
        in(p),in(l),in(r),in(c);
        if(p==0) sqr(l,r);
        else printf("%d\n",query(l,r));
    }
    return ~~(0^_^0);
}

LOJ #6281. 数列分块入门 5

原文：https://www.cnblogs.com/olinr/p/10069264.html