M_sea

洛谷2801 教主的魔法
Luogu分析大力分块。对于修改,边块直接暴力,整块打标记。对于查询,边块暴力查询,整块可以块内排序+块内二分。但...
扫描右侧二维码阅读全文
20
2018/12

洛谷2801 教主的魔法

Luogu

分析

大力分块。

对于修改,边块直接暴力,整块打标记。
对于查询,边块暴力查询,整块可以块内排序+块内二分。

但是每次查询都sort一遍极慢,可以先将每块排序后的数组存下来,当有一部分被修改时再重排一次。这样子就快了很多。

然后,块大小取$\sqrt{\frac{n+2}{3}}$,飞快。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=1000000+10;

int h[MAXN],g[MAXN];
int add[MAXN],belong[MAXN],L[MAXN],R[MAXN];

inline void copy(int x) {
    x=belong[x];
    for (re int i=L[x];i<=R[x];++i) g[i]=h[i];
    stable_sort(g+L[x],g+R[x]+1);
}

inline int find(int x,int v) { //在第x块中查询大于等于v的数量
    int left=L[x],right=R[x];
    while (left<=right) {
        int mid=(left+right)>>1;
        if (g[mid]<v) left=mid+1;
        else right=mid-1;
    }
    return R[x]-left+1;
}

int main() {
    int n=read(),q=read(),block=sqrt((n+2)/3.0);
    for (re int i=1;i<=n;++i) {
        h[i]=g[i]=read();
        belong[i]=(i-1)/block+1;
    }
    int cnt=0;
    for (re int i=1;i<=n;++i)
        if (belong[i]!=belong[i-1]) R[cnt]=i-1,L[++cnt]=i;
    R[cnt]=n;
    for (re int i=1;i<=cnt;++i) stable_sort(g+L[i],g+R[i]+1);
    while (q--) {
        char op[2]; scanf("%s",op);
        int l=read(),r=read(),x=read();
        if (op[0]=='M') { //修改
            if (belong[l]==belong[r]) {
                for (re int i=l;i<=r;++i) h[i]+=x; copy(l);
            } else {
                for (re int i=l;i<=R[belong[l]];++i) h[i]+=x; copy(l);
                for (re int i=L[belong[r]];i<=r;++i) h[i]+=x; copy(r);
                for (re int i=belong[l]+1;i<belong[r];++i) add[i]+=x;
            }
        } else { //查询
            int cnt=0;
            if (belong[l]==belong[r]) {
                for (re int i=l;i<=r;++i)
                    if (h[i]+add[belong[i]]>=x) ++cnt;
            } else {
                for (re int i=l;i<=R[belong[l]];++i)
                    if (h[i]+add[belong[i]]>=x) ++cnt;
                for (re int i=L[belong[r]];i<=r;++i)
                    if (h[i]+add[belong[i]]>=x) ++cnt;
                for (re int i=belong[l]+1;i<belong[r];++i) {
                    cnt+=find(i,x-add[i]);
                }
            }
            printf("%d\n",cnt);
        }
    }
    return 0;
}
最后修改:2019 年 01 月 03 日 02 : 01 PM

发表评论