分块及莫队题解

B - Time to Raid Cowavans

题意：给出n个数，p个询问。每个询问包含数字a、b，要求求出a，a+b，a+2b，……，a+nb的总和。
思路：对于b大于根号n的可以直接暴力，这个复杂度为s*sqrt(n)(s为这种的询问的个数)。对于b小于根号n的，可以先dp预处理出对于一个b的所有a的情况，然后o(1)询问，复杂度为n*sqrt(n)（二维dp会暴空间）。最坏情况时间复杂度为p*sqrt(n)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3 * 100010;
ll w[maxn],dp[maxn],ans[maxn];
ll n,p,bl;
struct Ques
{
    ll a,b,id;
}q[maxn];
vector<Ques>Q[maxn];
int main()
{
    scanf("%lld",&n);
    bl = sqrt(n);
    for(int i = 1;i <= n;i++)  scanf("%lld",&w[i]);
    scanf("%lld",&p);
    for(int i = 1;i <= p;i++)
    {
        scanf("%lld %lld",&q[i].a,&q[i].b);
        q[i].id = i;
        if(q[i].b >= bl)
        {
            ll sum = 0;
            ll a = q[i].a,b = q[i].b;
            for(int i = a;i <= n;i += b)  sum += w[i];
            ans[q[i].id] = sum;
        }
        else
        {
            Q[q[i].b].push_back(q[i]);
        }
    }
    for(int i = 1;i <= 600;i++)
    {
        for(int j = n;j >= 1;j--)
        {
            if(i + j > n)  dp[j] = w[j];
            else           dp[j] = dp[i + j] + w[j];
        }
        for(int j = 0;j < (int)Q[i].size();j++)  ans[Q[i][j].id] = dp[Q[i][j].a];
    }
    for(int i = 1;i <= p;i++)  printf("%lld\n",ans[i]);
    return 0;
}

C - GukiZ and GukiZiana

题意：给出n个数，q个操作。操作一把l，r区间的所有数加x。操作二询问数组中值等于y的两个数的最大距离，如果没有则输出-1。
思路：把区间分成根号n块，让每个块内的数有序。对于修改操作，被l，r跨过的区间只需要记录一个增加值add[i]，代表第i块的整体增量。未被跨过的区间不超过2*sqrt(n)，可以直接直接暴力修改。对于查询操作，只需要在每块区间二分查找y值，然后更新最小、最大的下标即可。总的时间复杂度O(nlog√n + q√n * log√n)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5 * 100010;
ll n,q,bl;
ll add[800],a[maxn],pos[maxn];
inline ll block(ll x)  {return (x - 1) / bl + 1;}
struct NODE
{
    ll w,id;
    bool operator< (const NODE &rhs) const
    {
        return w < rhs.w;
    }
}node[maxn];
int main()
{
    scanf("%lld %lld",&n,&q);
    bl = sqrt(n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%lld",&a[i]);
        node[i].w = a[i];
        node[i].id = i;
    }
    for(int i = 1;i <= block(n);i++)
    {
        sort(node + (i - 1) * bl + 1,node + min(i * bl,n) + 1);
    }
    for(int i = 1;i <= n;i++)  pos[node[i].id] = i;
    while(q--)
    {
        ll op,l,r,x;
        scanf("%lld",&op);
        if(op == 1)
        {
            scanf("%lld %lld %lld",&l,&r,&x);
            for(int i = block(l) + 1;i < block(r);i++)  add[i] += x;
            if(block(l) < block(r))
            {
                for(int i = l;i <= block(l) * bl;i++)  node[pos[i]].w += x;
                for(int i = (block(r) - 1) * bl + 1;i <= r;i++)  node[pos[i]].w += x;
                sort(node + (block(l) - 1) * bl + 1,node + min(block(l) * bl,n) + 1);
                sort(node + (block(r) - 1) * bl + 1,node + min(block(r) * bl,n) + 1);
                for(int i = (block(l) - 1) * bl + 1;i <= block(l) * bl;i++)  pos[node[i].id] = i;
                for(int i = (block(r) - 1) * bl + 1;i <= min(block(r) * bl,n);i++)  pos[node[i].id] = i;
            }
            else
            {
                for(int i = l; i <= r; i++)  node[pos[i]].w += x;
                sort(node + (block(l) - 1) * bl + 1,node + min(block(l) * bl,n) + 1);
                for(int i = (block(l) - 1) * bl + 1; i <= min(block(l) * bl,n); i++)  pos[node[i].id] = i;
            }
        }
        else
        {
            struct NODE temp;
            scanf("%lld",&x);
            ll minl = maxn,maxr = 0;
            for(int i = 1;i <= block(n);i++)
            {
                temp.w = x - add[i];
                ll pl = lower_bound(node + (i - 1) * bl + 1,min(i * bl,n) + node + 1,temp) - node;
                ll pr = upper_bound(node + (i - 1) * bl + 1,min(i * bl,n) + node + 1,temp) - node;
                for(int j = pl;j < pr;j++)
                {
                    minl = min(minl,node[j].id);
                    maxr = max(maxr,node[j].id);
                }
            }
            if(minl == maxn && maxr == 0)
                printf("-1\n");
            else
                printf("%lld\n",maxr - minl);
        }
    }
    return 0;
}