题解：SP28265 ADARAIN - Ada and Rain

· · 题解

题意

有一个长为 w 的数列，起初都为 0；有 n 次操作，将 l 到 r 间的数都加上 1；然后又 m 次询问，问第 a 个数是多少。

思路

此题就是区间操作，线段树，树状数组都可以写。最近我刚学分块，就用分块讲吧！不过分块确实好理解又好写

  1. 初始化分块，将数列分为几块，每块的左右端点以及每个点在第几块都处理好。这里建议分为 \sqrt{w} 块，对于尾部不足一块的，再组建一个块。
  2. 修改时，如果 l 和 r 在一块内，就暴力修改；否则将没有覆盖一整块的部分暴力加，中间整块用 add_i 存储表示第 i 块整体加了多少。
  3. 单点查询就求这个点的值再加上他所在块整体加上的 add_i 即可。

由于使用了 add_i 对整块的处理，所以复杂度为 O(n\sqrt{n})。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+5;
int add[5000],L[5000],R[5000],a[N],pos[N];
int n,m,w;
int read()// 快读
{
    int t=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}
void init()// 初始化
{
    int t=sqrt(w);
    for(int i=1;i<=t;i++)
    {
        L[i]=R[i-1]+1;
        R[i]=i*t;
    }
    if(R[t]<w)
    {
        t++;
        R[t]=w;
        L[t]=R[t-1]+1;
    }
    for(int i=1;i<=t;i++)
    {
        for(int j=L[i];j<=R[i];j++)
        {
            pos[j]=i;
        }
    }
}
void change(int l,int r)// 修改
{
    int p=pos[l],q=pos[r];
    if(p==q)// 在同一块
    {
        for(int i=l;i<=r;i++)
        {
            a[i]++;
        }
    }
    else
    {
        for(int i=l;i<=R[p];i++) a[i]++;
        for(int i=L[q];i<=r;i++) a[i]++;
        for(int i=p+1;i<=q-1;i++) add[i]++;
    }
}
signed main()
{
    n=read();
    m=read();
    w=read();
    init();
    for(int i=1;i<=n;i++)
    {
        int l=read();
        int r=read();
        change(l,r);
    }
    for(int i=1;i<=m;i++)
    {
        int x=read();
        printf("%lld\n",a[x]+add[pos[x]]);
    }
    return 0;
}

建议评绿或黄