【luogu P2801】教主的魔法

左手的ㄟ右手 2021-12-09 07:27 275阅读 0赞

传送门：[https://www.luogu.org/problemnew/show/P2801][https_www.luogu.org_problemnew_show_P2801]

这道题刚看到的时候感觉就是线段树的两种操作嘛，维护一棵线段树就好了。然并卵我忘记线段树怎么写了。然后就想到打暴力水过数据点，就花了十来分钟打暴力，搞过了样例。但是。。。。最后得了0分，其他巨佬同样写了暴力拿到了100分（果然是我太菜了）。

后来改题的时候看了眼题解，说是要用分块（早已遗忘了分块），然后就花了挺长时间写了分块，在洛谷上提交还是tle了一个点，但是算了一下复杂度是O(msqrt(nlogn))，并没有超数据范围（咱也不知道，咱也不敢问QAQ）最后开了o2，那个点就过了（玄学）。。。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<cmath>
    #include<queue>
    #include<vector>
    #include<cstring>
    typedef long long ll;
    using namespace std;
    const int maxn = 1000005;
    int n, m, block;
    int v[maxn], bel[maxn], tag[maxn];
    vector<int>vec[10005];
    void reset(int x) {
        vec[x].clear();
        for(int i = (x - 1) * block + 1; i <= min(x * block,n); i++)
            vec[x].push_back(v[i]);
        sort(vec[x].begin(),vec[x].end());
    }
    ll read()                               
    {
        ll x=0,f=1;char ch=getchar();
        while(ch<'0'||ch>'9'){
         if(ch=='-')f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
        return x*f;
    }
    void add(int a, int b, int c) {
        for(int i = a; i <= min(bel[a] * block,b); i++)
            v[i] += c;
        reset(bel[a]);
        if(bel[a] != bel[b]) {
            for(int i = (bel[b] - 1) * block + 1; i <= b; i++)
                v[i] += c;
            reset(bel[b]);
        }
        for(int i = bel[a]+ 1; i <= bel[b] - 1; i++)
            tag[i] += c;
    }
    int query(int a, int b, int c) {
        int ans = 0;
        for(int i = a; i <= min(bel[a] * block,b); i++)
            if(v[i] + tag[bel[a]] < c)
                ans++;
        if(bel[a] != bel[b]) {
            for(int i = (bel[b] - 1) * block + 1; i <= b; i++)
                if(v[i] + tag[bel[b]] < c)
                    ans++;
        }
        for(int i = bel[a] + 1; i <= bel[b] - 1; i++) {
            int x = c - tag[i];
            ans += lower_bound(vec[i].begin(),vec[i].end(),x) - vec[i].begin();
        }
        return ans;
    }
    int main() {
        n = read(), m = read();
        block = sqrt(n);
        for(int i = 1; i <= n; i++)
            v[i] = read();
        for(int i = 1; i <= n; i++) {
            bel[i] = (i - 1) / block + 1;
            vec[bel[i]].push_back(v[i]);
        }
        for(int i = 1; i <= bel[n]; i++)
            sort(vec[i].begin(),vec[i].end());
        for(int i = 1; i <= m; i++) {
            char f[5];
            scanf("%s", f);
            int a = read(), b = read(), c = read();
            if(f[0] == 'M')
                add(a,b,c);
            else
                printf("%d\n",b - a + 1 - query(a,b,c));
        }
        return 0;
    }

转载于:https://www.cnblogs.com/jiqimin/p/10992770.html

[https_www.luogu.org_problemnew_show_P2801]: https://www.luogu.org/problemnew/show/P2801
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211208/f10913290a364528b648d24c5fdb49fe.png