数列分块入门

题目链接：https://loj.ac/problem/6277

内存限制：256 MiB时间限制：100 ms标准输入输出

给出一个长为

第一行输入一个数字

第二行输入 $a_iai，以空格隔开。$

接下来输入

若

若 $a_rar 的值（ll 和 cc 忽略）。$

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

样例输入

样例输出

2
5

对于 $231≤others、ans<=2^{31}-1ans≤231−1。$

解题思路：首先暴力肯定超时，这应该都知道，但这题完全可以采用线段树来做，用区间更新加单点查找就可以了。但是既然题目写了数列分块入门，我们就用分块的思想来写，分块其实也就是暴力的一种优化，数列的长度为n，我们可以把它分成若干块。

先理解下概念，完整块：被操作区间完全覆盖的块，不完整块：操作区间不完全覆盖的块，对于完整块，我们可以直接用懒惰标记更新，询问时只要找到该元素的值加上该元素所在块的懒惰标记值就可以了，而对于不完整块，元素个数较少，我们可以暴力更新。假设我们将n个元素为m块，那么每个块的大小为n/m，当我们进行更新时，我们先暴力更新区间左端点到该点所在块的右端点，再暴力更新右端点所在块的左端点到区间右端点，操作的复杂度为O(n/m),再对完整块整块整块进行更新，之多含有m块，复杂度为O(m),所以总的复杂度为O(n+n/m)，根据均值不等式，当m=sqrt(n)时，复杂度最低。

如上图区间，分为了5个块，当对区间[L,R]更新时，可以先暴力暴力更新[L,x2],和[x5,R],然后再对块2-块4进行更新。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<cmath>
#include<list>
#include<deque>
#include<cstdlib>
#include<bitset>
#include<stack>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define pushup() tree[rt]=tree[rt<<1]+tree[rt<<1|1]
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const ll mod=1e9+7;
const int maxn=1000005;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m,q,tot,ans,block,num,l[maxn],r[maxn],belong[maxn];
ll a[maxn],lazy[maxn];
/*
a[i]数列元素
lazy[i]为第i块的懒惰标记
num分块的个数
belong[i]表示i属于哪一块
block表示块的大小
l[i]表示i这块左端点位置
r[i]表示i这块右端点位置
*/
void build()
{
    block=sqrt(n);  //每个块的大小为sqrt(n)
    num=n/block; if(n%block)num++;  //最后一块大小可能小于block
    for(int i=1;i<=num;i++)
        l[i]=(i-1)*block+1,r[i]=i*block;  //计算每个块的左右边界
    r[num]=n;  //最后一块右边界可能不为num*block,总共有n个元素，应设为n
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;  //计算每个元素所属块

}
void update(int x,int y,ll C)
{
    if(belong[x]==belong[y])  //如果左端点和右端点属于同一块，直接暴力更新
    {
        for(int i=x;i<=y;i++)
            a[i]+=C;
        return;
    }
    for(int i=x;i<=r[belong[x]];i++) //暴力更新最左边的不完整块
        a[i]+=C;
    for(int i=belong[x]+1;i<belong[y];i++)//懒惰标记更新中间的完整块
        lazy[i]+=C;
    for(int i=l[belong[y]];i<=y;i++)//暴力更新最右边的不完整块
        a[i]+=C;
}
long long query(int x)
{
    return a[x]+lazy[belong[x]];
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    build();
    int m=n;
    while(m--)
    {
        int opt,x,y; ll c;
        cin>>opt>>x>>y>>c;
        if(opt==0)update(x,y,c);
        else printf("%lld
",query(y));
    }
    return 0;
}

题目链接：https://loj.ac/problem/6278

内存限制：256 MiB时间限制：500 ms标准输入输出

给出一个长为

第一行输入一个数字

第二行输入 $a_iai，以空格隔开。$

接下来输入

若

若 $c^2c2 的数字的个数。$

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

样例输入

样例输出

3
0
2

对于 $100\%100% 的数据，1 leq n leq 50000, -2^{31} leq mathrm{others}1≤n≤50000,−231≤others、mathrm{ans} leq 2^{31}-1ans≤231−1。$

解题思路：对于不完整块，我们可以直接暴力查找小于c*c的个数，而对于完整块，我们可以将每个块的所有元素放入该块对应的容器中，然后对每个容器进行排序，然后便可以用二分来查找块内的元素了。需要注意的是，对于更新操作，如果是完整块，全部元素同时加上一个值，不该变块内元素的相对大小，可以不用重新排序，而对于不完整块，会改变块内元素的相对大小，需要对该块元素进行重新排序。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<cmath>
#include<list>
#include<deque>
#include<cstdlib>
#include<bitset>
#include<stack>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define pushup() tree[rt]=tree[rt<<1]+tree[rt<<1|1]
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const ll mod=1e9+7;
const int maxn=1000005;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m,q,tot,ans,block,num,l[maxn],r[maxn],belong[maxn];
ll a[maxn],lazy[maxn];
vector<ll> vec[50005];
/*
num分块的个数
belong[i]表示i属于哪一块
block表示块的大小
l[i]表示i这块左端点位置
r[i]表示i这块右端点位置
vec[i]存放第i块的所有元素
*/
void build()
{
    block=sqrt(n);  //每个块的大小为sqrt(n)
    num=n/block; if(n%block)num++; //最后一块大小可能小于block
    r[num]=n;  //最后一块右边界可能不为num*block,总共有n个元素，应设为n
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1,vec[belong[i]].push_back(a[i]); //计算每个元素所属块,并将元素存放在所属块容器
    for(int i=1;i<=num;i++)
        l[i]=(i-1)*block+1,r[i]=i*block,sort(vec[i].begin(),vec[i].end()); //计算每个块的左右边界，并对每块元素进行排序

}
void resort(int x)
{  //对第x块元素重新排序
    vec[x].clear();
    for(int i=l[x];i<=r[x];i++)
        vec[x].push_back(a[i]);
    sort(vec[x].begin(),vec[x].end());
}
void update(int x,int y,ll C)
{
    if(belong[x]==belong[y])
    {  //x和y属于同一块直接暴力更新
        for(int i=x;i<=y;i++)
            a[i]+=C;
        resort(belong[x]);  //对x所在 块重新排序
        return;
    }
    for(int i=x;i<=r[belong[x]];i++) //暴力更新x所在块
        a[i]+=C;
    for(int i=belong[x]+1;i<belong[y];i++)//更新中间块
        lazy[i]+=C;
    for(int i=l[belong[y]];i<=y;i++) //暴力更新y所在块
        a[i]+=C;
    //分别对x所在块和y所在块重新排序
    resort(belong[x]);
    resort(belong[y]);
}
int query(int x,int y,ll c)
{ //注意查找时每个元素需要加上所在块的懒惰标记值再进行比较
    int ans=0;
    if(belong[x]==belong[y])
    {//x和y属于同一块，暴力求解
        for(int i=x;i<=y;i++)
            if(a[i]+lazy[belong[i]]<c)ans++;
        return ans;
    }
    for(int i=x;i<=r[belong[x]];i++)
        if(a[i]+lazy[belong[i]]<c)ans++;
    //注意查找的是小于c-lazy[i]的个数
    //a[i]+lazy[belong[i]]<c  ->   a[i]<c-lazy[belong[i]]
    for(int i=belong[x]+1;i<belong[y];i++)
        ans+=lower_bound(vec[i].begin(),vec[i].end(),c-lazy[i])-vec[i].begin();
    for(int i=l[belong[y]];i<=y;i++)
        if(a[i]+lazy[belong[i]]<c)ans++;
    return ans;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    build();
    int m=n;
    while(m--)
    {
        int opt,x,y; ll c;
        cin>>opt>>x>>y>>c;
        if(opt==0)update(x,y,c);
        else printf("%d
",query(x,y,c*c));
    }
    return 0;
}

View Code

题目链接：https://loj.ac/problem/6279

内存限制：256 MiB时间限制：1500 ms标准输入输出

给出一个长为

第一行输入一个数字

第二行输入 $a_iai，以空格隔开。$

接下来输入

若

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

样例输入

样例输出

3
-1

对于 $100\%100% 的数据，1 leq n leq 100000, -2^{31} leq mathrm{others}1≤n≤100000,−231≤others、mathrm{ans} leq 2^{31}-1ans≤231−1。$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<cmath>
#include<list>
#include<deque>
#include<cstdlib>
#include<bitset>
#include<stack>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define pushup() tree[rt]=tree[rt<<1]+tree[rt<<1|1]
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const ll mod=1e9+7;
const int maxn=1000005;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m,q,tot,ans,block,num,l[maxn],r[maxn],belong[maxn];
int a[maxn],lazy[maxn];
vector<int> vec[50005];
bool cmp(int a,int b){return a>b;}
/*
num分块的个数
belong[i]表示i属于哪一块
block表示块的大小
l[i]表示i这块左端点位置
r[i]表示i这块右端点位置
vec[i]存放第i块的所有元素
*/
void build()
{
    block=sqrt(n);  //每个块的大小为sqrt(n)
    num=n/block; if(n%block)num++; //最后一块大小可能小于block
    r[num]=n;  //最后一块右边界可能不为num*block,总共有n个元素，应设为n
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1,vec[belong[i]].push_back(a[i]); //计算每个元素所属块,并将元素存放在所属块容器
    for(int i=1;i<=num;i++)
        l[i]=(i-1)*block+1,r[i]=i*block,sort(vec[i].begin(),vec[i].end()); //计算每个块的左右边界，并对每块元素进行排序

}
void resort(int x)
{  //对第x块元素重新排序
    vec[x].clear();
    for(int i=l[x];i<=r[x];i++)
        vec[x].push_back(a[i]);
    sort(vec[x].begin(),vec[x].end());
}
void update(int x,int y,ll C)
{
    if(belong[x]==belong[y])
    {  //x和y属于同一块直接暴力更新
        for(int i=x;i<=y;i++)
            a[i]+=C;
        resort(belong[x]);  //对x所在 块重新排序
        return;
    }
    for(int i=x;i<=r[belong[x]];i++) //暴力更新x所在块
        a[i]+=C;
    for(int i=belong[x]+1;i<belong[y];i++)//更新中间块
        lazy[i]+=C;
    for(int i=l[belong[y]];i<=y;i++) //暴力更新y所在块
        a[i]+=C;
    //分别对x所在块和y所在块重新排序
    resort(belong[x]);
    resort(belong[y]);
}
int query(int x,int y,ll c)
{ //注意查找时每个元素需要加上所在块的懒惰标记值再进行比较
    int ans=-1;
    if(belong[x]==belong[y])
    {//x和y属于同一块，暴力求解
        for(int i=x;i<=y;i++)
            if(a[i]+lazy[belong[i]]<c)
                ans=max(ans,a[i]+lazy[belong[i]]);
        return ans;
    }
    for(int i=x;i<=r[belong[x]];i++)
        if(a[i]+lazy[belong[i]]<c)
            ans=max(ans,a[i]+lazy[belong[i]]);
    for(int i=belong[x]+1;i<belong[y];i++)
    {
        int pos=lower_bound(vec[i].begin(),vec[i].end(),c-lazy[i])-vec[i].begin();
        //pos为第一个大于等于c-lazy[i]的位置
        if(pos>=1) ans=max(ans,vec[i][pos-1]+lazy[i]);
    }
    for(int i=l[belong[y]];i<=y;i++)
        if(a[i]+lazy[belong[i]]<c)
            ans=max(ans,a[i]+lazy[belong[i]]);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    build();
    int m=n;
    while(m--)
    {
        int opt,x,y; ll c;
        cin>>opt>>x>>y>>c;
        if(opt==0)update(x,y,c);
        else printf("%d
",query(x,y,c));
    }
    return 0;
}

View Code

题目链接：https://loj.ac/problem/6280

内存限制：256 MiB时间限制：500 ms标准输入输出

给出一个长为

第一行输入一个数字

第二行输入 $a_iai，以空格隔开。$

接下来输入

若

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

样例输入

样例输出

1
4

对于 $100\%100% 的数据，1 leq n leq 50000, -2^{31} leq mathrm{others}1≤n≤50000,−231≤others、mathrm{ans} leq 2^{31}-1ans≤231−1。$

$解题思路：用一个数组存储每个块所有元素的和，然后维护每个块的元素和就好了$

$代码：$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<cmath>
#include<list>
#include<deque>
#include<cstdlib>
#include<bitset>
#include<stack>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define pushup() tree[rt]=tree[rt<<1]+tree[rt<<1|1]
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const ll mod=1e9+7;
const int maxn=1000005;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m,q,tot,ans,block,num,l[maxn],r[maxn],belong[maxn];
ll a[maxn],Sum[maxn],lazy[maxn];
/*
num分块的个数
belong[i]表示i属于哪一块
block表示块的大小
l[i]表示i这块左端点位置
r[i]表示i这块右端点位置
Sum[i]表示第i块所有元素的和
*/
void build()
{
    block=sqrt(n); 
    num=n/block; if(n%block)num++;
    r[num]=n;
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;
    for(int i=1;i<=num;i++)
        l[i]=(i-1)*block+1,r[i]=i*block;

    for(int i=1;i<=num;i++)
        for(int j=l[i];j<=r[i];j++)
            Sum[i]+=a[j];
}
void update(int x,int y,ll C)
{
    if(belong[x]==belong[y])
    {
        for(int i=x;i<=y;i++)
            a[i]+=C;
        Sum[belong[x]]+=C*(y-x+1);
        return;
    }
    for(int i=x;i<=r[belong[x]];i++)
        a[i]+=C;
    for(int i=belong[x]+1;i<belong[y];i++)
        lazy[i]+=C;
    for(int i=l[belong[y]];i<=y;i++)
        a[i]+=C;
    Sum[belong[x]]+=C*(r[belong[x]]-x+1);
    Sum[belong[y]]+=C*(y-l[belong[y]]+1);
}
ll query(int x,int y,ll c)
{
    ll ans=0;
    if(belong[x]==belong[y])
    {
        for(int i=x;i<=y;i++)
            ans=(ans+a[i]+lazy[belong[i]])%(c+1);
        return ans;
    }
    for(int i=x;i<=r[belong[x]];i++)
        ans=(ans+a[i]+lazy[belong[i]])%(c+1);
    for(int i=belong[x]+1;i<belong[y];i++)
        ans=(ans+Sum[i]+lazy[i]*block)%(c+1);
    for(int i=l[belong[y]];i<=y;i++)
        ans=(ans+a[i]+lazy[belong[i]])%(c+1);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    build();
    int m=n;
    while(m--)
    {
        int opt,x,y; ll c;
        cin>>opt>>x>>y>>c;
        if(opt==0)update(x,y,c);
        else printf("%lld
",query(x,y,c));
    }
    return 0;
}

View Code

内存限制：256 MiB时间限制：500 ms标准输入输出

题目类型：传统评测方式：文本比较

上传者： hzwer

提交提交记录统计测试数据讨论

给出一个长为 $a_1ldots a_na1…an，以及 nn 个操作，操作涉及区间开方，区间求和。$

第一行输入一个数字

第二行输入 $a_iai，以空格隔开。$

接下来输入

若 $a_i(lle ile r),: a_i ← leftlfloor sqrt{a_i} ight floorai(l≤i≤r),ai←⌊ai⌋$

若

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

样例输入

样例输出

6
2

对于 $100\%100% 的数据，1 leq n leq 50000, -2^{31} leq mathrm{others}1≤n≤50000,−231≤others、mathrm{ans} leq 2^{31}-1ans≤231−1。$

$解题思路：这个题目有点小技巧，还挺难想到的。我们可以发现对每个数开方是非常复杂的，我们无法从每个块元素原来的和推出它们开方之后的和，题目说每个元素开方之后都是向下取整，所以我们观察数据范围，最大2的31次方，最多只能开5次方，变全部会变成0或1，所以我们只要加一个标记，标记每个块的元素是否全部已经变为0或1了，区间修改直接跳过全部变为0或1的块就行了，而对于前几次开方，我们可以直接暴力对每个元素进行开方，完全不会超时的。$

$代码：$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<cmath>
#include<list>
#include<deque>
#include<cstdlib>
#include<bitset>
#include<stack>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define pushup() tree[rt]=tree[rt<<1]+tree[rt<<1|1]
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const ll mod=1e9+7;
const int maxn=1000005;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m,q,tot,ans,block,num,l[maxn],r[maxn],belong[maxn];
ll a[maxn],Sum[maxn],vis[maxn];
/*
num分块的个数
belong[i]表示i属于哪一块
block表示块的大小
l[i]表示i这块左端点位置
r[i]表示i这块右端点位置
Sum[i]表示第i块所有元素的和
vis[i]标记第i块元素是否已经全为0
*/
void build()
{
    block=sqrt(n);
    num=n/block; if(n%block)num++;
    r[num]=n;
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;
    for(int i=1;i<=num;i++)
        l[i]=(i-1)*block+1,r[i]=i*block;

    for(int i=1;i<=num;i++)
        for(int j=l[i];j<=r[i];j++)
            Sum[i]+=a[j];
}
void update(int x,int y)
{
    if(belong[x]==belong[y])
    {
        if(vis[belong[x]])return;
        ll tmp=0;
        for(int i=x;i<=y;i++)
            tmp+=a[i]-(ll)sqrt(a[i]),a[i]=sqrt(a[i]);
        Sum[belong[x]]-=tmp;
        return;
    }
    ll tmp=0;
    if(!vis[belong[x]])
        for(int i=x;i<=r[belong[x]];i++)
            tmp+=a[i]-(ll)sqrt(a[i]),a[i]=sqrt(a[i]);
    Sum[belong[x]]-=tmp;
    for(int i=belong[x]+1;i<belong[y];i++)
    {
        tmp=0;
        if(vis[i])continue;
        for(int j=l[i];j<=r[i];j++)
            tmp+=a[j]-(ll)sqrt(a[j]),a[j]=sqrt(a[j]);
        Sum[i]-=tmp;
        if(tmp==0)vis[i]=1;  //tmp为0表示Sum[i]并未改变，即块内元素已经全部变为0或1了
    }
    tmp=0;
    if(!vis[belong[y]])
        for(int i=l[belong[y]];i<=y;i++)
            tmp+=a[i]-(ll)sqrt(a[i]),a[i]=sqrt(a[i]);
    Sum[belong[y]]-=tmp;
}
ll query(int x,int y)
{
    ll ans=0;
    if(belong[x]==belong[y])
    {
        for(int i=x;i<=y;i++)
            ans=ans+a[i];
        return ans;
    }
    for(int i=x;i<=r[belong[x]];i++)
        ans+=a[i];
    for(int i=belong[x]+1;i<belong[y];i++)
        ans+=Sum[i];
    for(int i=l[belong[y]];i<=y;i++)
        ans+=a[i];
    return ans;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    build();
    int m=n;
    while(m--)
    {
        int opt,x,y; ll c;
        cin>>opt>>x>>y>>c;
        if(opt==0)update(x,y);
        else printf("%lld
",query(x,y));
    }
    return 0;
}

View Code

题目链接：https://loj.ac/problem/6282

内存限制：256 MiB时间限制：500 ms标准输入输出

给出一个长为

第一行输入一个数字

第二行输入 $a_iai，以空格隔开。$

接下来输入

若

若 $a_rar 的值（ll 和 cc 忽略）。$

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

样例输入

样例输出

2
3

对于 $100\%100% 的数据，1 leq n leq 100000, -2^{31} leq mathrm{others}1≤n≤100000,−231≤others、mathrm{ans} leq 2^{31}-1ans≤231−1。$

解题思路：我们把每一个块的元素单独放入一个数组，然后每次插入一个元素就直接暴力插入，后面的全部元素后移。查找位置时就只要把每个数组的长度凑一凑，就知道在哪个块的哪个位置。不过这题有个难点就是有可能一个块会插入很多元素，然后对那个块插入元素的复杂度便无法控制了，所以当插入元素超过块的大小时，我们需要对这些元素重新分块。这样复杂度便得到保证了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<cmath>
#include<list>
#include<deque>
#include<cstdlib>
#include<bitset>
#include<stack>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define pushup() tree[rt]=tree[rt<<1]+tree[rt<<1|1]
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const ll mod=1e9+7;
const int maxn=1000005;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m,q,tot,ans,block,num,l[maxn],r[maxn],belong[maxn],len[maxn];
int a[1105][3005],b[1105][3005],Sum[maxn],vis[maxn];
/*
num分块的个数
belong[i]表示i属于哪一块
block表示块的大小
*/
void build()
{
    block=sqrt(n); m=n;
    num=n/block; if(n%block)num++;
    //r[num]=n;
    for(int i=1;i<=n;i++)
    {
        int kuai=(i-1)/block+1;//计算该元素在第几块
        int x=0; cin>>x;
        a[kuai][++len[kuai]]=x;
    }
    //for(int i=1;i<=num;i++)
        //l[i]=(i-1)*block+1,r[i]=i*block;
}
void rebuild()
{
    m+=tot; tot=0;  //总元素数量加tot
    block=(int)sqrt(m); //块大小改变成sqrt(m)
    int cnt=0,lenth=0;
    for(int i=1;i<=num;i++)
        for(int j=1;j<=len[i];j++)
        {
            cnt++;
            int id=(cnt-1)/block+1; //计算重新分块后该元素所在块
            b[id][++lenth]=a[i][j];
            if(lenth==block)lenth=0; //第id个块已经满，进入下一块起始位置
        }
    num=m/block; if(m%block)num++;  //计算重新分块的数目
    for(int i=1;i<=num;i++)
    {
        if(i!=num||m%block==0)len[i]=block;
        else len[i]=m-block*block;
        for(int j=1;j<=len[i];j++)a[i][j]=b[i][j];
    }
}
void update(int x,int y)
{
    int i,pos=0;
    for(i=1;i<=block;i++)
    {
        if(pos+len[i]>=x)break;
        pos+=len[i];
    }
    len[i]++;
    for(int j=len[i];j>=x-pos+1;j--)
        a[i][j]=a[i][j-1];
    a[i][x-pos]=y;
    tot++;
    if(tot==block)rebuild();  //重新分块
}
ll query(int x)
{
    int i,pos=0;
    for(i=1;i<=num;i++)
    {
        if(pos+len[i]>=x)break;
        pos+=len[i];
    }
    return a[i][x-pos];
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    tot=0;
    build();
    int m=n;
    for(int i=1;i<=m;i++)
    {
        int opt,x,y; int c;
        cin>>opt>>x>>y>>c;
        if(opt==0)update(x,y);
        else printf("%d
",query(y));
    }
    return 0;
}

View Code

题目链接：https://loj.ac/problem/6283

内存限制：256 MiB时间限制：500 ms标准输入输出

给出一个长为

第一行输入一个数字

第二行输入 $a_iai，以空格隔开。$

接下来输入

若

若 $a_rar 的值 mod 10007mod 10007（ll 和 cc 忽略）。$

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

样例输入

7
1 2 2 3 9 3 2
0 1 3 1
2 1 3 1
1 1 4 4
0 1 7 2
1 2 6 4
1 1 6 5
2 2 6 4

样例输出

3
100

对于 $100\%100% 的数据，1 leq n leq 100000, -2^{31} leq mathrm{others}1≤n≤100000,−231≤others、mathrm{ans} leq 2^{31}-1ans≤231−1。$

$解题思路：这题是在数列分块入门1中加了一种区间乘法操作，我们只要考虑如何同时维护好这两种标记就好了。我们得先取个优先级，加法优先是无法维护的，所以我们考虑乘法优先，当我们一个完整块进行加法时可以直接加到加法标记中，而当我们对一个完整块进行乘法时，需要同时对乘法标记和加法标记做乘法。当我们对于不完整块更新时，一定要先下推清除整个块的加法标记和乘法标记才能进行暴力更新。$

$代码：$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<cmath>
#include<list>
#include<deque>
#include<cstdlib>
#include<bitset>
#include<stack>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define pushup() tree[rt]=tree[rt<<1]+tree[rt<<1|1]
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const ll mod=10007;
const int maxn=1000005;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m,q,tot,ans,block,num,l[maxn],r[maxn],belong[maxn];
ll a[maxn],add[maxn],mul[maxn];
/*
num分块的个数
belong[i]表示i属于哪一块
block表示块的大小
l[i]表示i这块左端点位置
r[i]表示i这块右端点位置
add[i]第i块的加法标记
mul[i]第i块的乘法标记
*/
void build()
{
    block=sqrt(n);
    num=n/block; if(n%block)num++;
    r[num]=n;
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;
    for(int i=1;i<=num;i++)
        l[i]=(i-1)*block+1,r[i]=i*block;
}
void pushdown(int x)
{ //下推，去除标记
    for(int i=l[x];i<=r[x];i++)
        a[i]=(a[i]*mul[x]%mod+add[x])%mod;
    mul[x]=1; add[x]=0;  //更新标记
}
void update(int opt,int x,int y,ll C)
{
    if(opt==0){
        if(belong[x]==belong[y])
        {
            pushdown(belong[x]);
            for(int i=x;i<=y;i++)
                a[i]=(a[i]+C)%mod;
            return;
        }
        pushdown(belong[x]);
        for(int i=x;i<=r[belong[x]];i++)
            a[i]=(a[i]+C)%mod;
        for(int i=belong[x]+1;i<belong[y];i++)
            add[i]=(add[i]+C)%mod;
        pushdown(belong[y]);
        for(int i=l[belong[y]];i<=y;i++)
            a[i]=(a[i]+C)%mod;
    }
    else{
        if(belong[x]==belong[y])
        {
            pushdown(belong[x]);
            for(int i=x;i<=y;i++)
                a[i]=a[i]*C%mod;
            return;
        }
        pushdown(belong[x]);
        for(int i=x;i<=r[belong[x]];i++)
            a[i]=a[i]*C%mod;
        for(int i=belong[x]+1;i<belong[y];i++)
            mul[i]=mul[i]*C%mod,add[i]=add[i]*C%mod;
        pushdown(belong[y]);
        for(int i=l[belong[y]];i<=y;i++)
            a[i]=a[i]*C%mod;
    }
}
ll query(int x)
{
    return (a[x]%mod*mul[belong[x]]%mod+add[belong[x]])%mod;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],mul[i]=1;
    build();
    int m=n;
    while(m--)
    {
        int opt,x,y; ll c;
        cin>>opt>>x>>y>>c;
        if(opt!=2)update(opt,x,y,c);
        else printf("%lld
",query(y));
    }
    return 0;
}

View Code

题目链接：https://loj.ac/problem/6284

内存限制：256 MiB时间限制：500 ms标准输入输出

给出一个长为

第一行输入一个数字

第二行输入 $a_iai，以空格隔开。$

接下来输入

表示先查询位于

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

样例输入

样例输出

对于 $100\%100% 的数据，1 leq n leq 100000, -2^{31} leq mathrm{others}1≤n≤100000,−231≤others、mathrm{ans} leq 2^{31}-1ans≤231−1。$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<cmath>
#include<list>
#include<deque>
#include<cstdlib>
#include<bitset>
#include<stack>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define pushup() tree[rt]=tree[rt<<1]+tree[rt<<1|1]
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const ll mod=10007;
const int maxn=1000005;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,m,q,tot,block,num,l[maxn],r[maxn],belong[maxn];
ll a[maxn],vis[maxn],lazy[maxn];
/*
num分块的个数
belong[i]表示i属于哪一块
block表示块的大小
l[i]表示i这块左端点位置
r[i]表示i这块右端点位置
vis[i]标记第i块是否全为同一个数
lazy[i]标记第i块元素的值
*/
void build()
{
    block=sqrt(n);
    num=n/block; if(n%block)num++;
    r[num]=n;
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;
    for(int i=1;i<=num;i++)
        l[i]=(i-1)*block+1,r[i]=i*block;
}
void pushdown(int x)  //下推清除标记
{
    if(vis[x]==0) return;
    for(int i=l[x];i<=r[x];i++)
        a[i]=lazy[x];
    vis[x]=0; lazy[x]=INF;
}
int update(int x,int y,ll c)
{
    int ans=0;
    if(belong[x]==belong[y])
    {
        pushdown(belong[x]);
        for(int i=x;i<=y;i++)
        {
            if(a[i]==c)ans++;
            a[i]=c;
        }
        return ans;
    }
    pushdown(belong[x]);
    for(int i=x;i<=r[belong[x]];i++)
    {
        if(a[i]==c)ans++;
        else a[i]=c;
    }
    pushdown(belong[y]);
    for(int i=l[belong[y]];i<=y;i++)
    {
        if(a[i]==c)ans++;
        else a[i]=c;
    }
    for(int i=belong[x]+1;i<belong[y];i++)
    {
        if(vis[i]!=0){
            if(lazy[i]==c)ans+=block;
            lazy[i]=c;
        }
        else{
            for(int j=l[i];j<=r[i];j++)
            {
                if(a[j]==c)ans++;
                else a[j]=c;
            }
            vis[i]=1; lazy[i]=c;
        }
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        vis[i]=0;
        lazy[i]=INF;
    }
    build();
    int m=n;
    while(m--)
    {
        int x,y; ll c;
        cin>>x>>y>>c;
        cout<<update(x,y,c)<<endl;
    }
    return 0;
}

View Code