LOJ #6283. 数列分块入门 7-分块(区间乘法、区间加法、单点查询)

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

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

上传者： hzwer

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

给出一个长为

第一行输入一个数字

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

接下来输入

若

若 $a_rar 的值 mathop{mathrm{mod}} 10007mod10007（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。$

这道题要开比1e5大，要不然过不去，真实测试。。。

  1 //#6283. 数列分块入门 7-区间乘法，区间加法，单点查询-要开1e6，mdzz
  2 #include<bits/stdc++.h>
  3 using namespace std;
  4 typedef long long ll;
  5 const int maxn=1e6+10;
  6 
  7 int n,m;
  8 int a[maxn],add[maxn],mul[maxn],pos[maxn];
  9 const int mod=10007;
 10 
 11 void update_add(int l,int r,int c)
 12 {
 13     if(pos[l]==pos[r]){
 14         for(int i=(pos[l]-1)*m+1;i<=pos[l]*m;i++){
 15             a[i]=(a[i]*mul[pos[l]]%mod+add[pos[l]]+mod)%mod;
 16         }
 17         for(int i=l;i<=r;i++)
 18             a[i]=(a[i]+c+mod)%mod;
 19         mul[pos[l]]=1;add[pos[l]]=0;
 20     }
 21     else{
 22         for(int i=(pos[l]-1)*m+1;i<=pos[l]*m;i++){
 23             a[i]=(a[i]*mul[pos[l]]%mod+add[pos[l]]+mod)%mod;
 24         }
 25         for(int i=l;i<=pos[l]*m;i++)
 26             a[i]=(a[i]+c+mod)%mod;
 27         mul[pos[l]]=1;add[pos[l]]=0;
 28         for(int i=pos[l]+1;i<pos[r];i++){
 29             add[i]=(add[i]+c+mod)%mod;
 30         }
 31         for(int i=(pos[r]-1)*m+1;i<=min(pos[r]*m,n);i++){
 32             a[i]=(a[i]*mul[pos[r]]%mod+add[pos[r]]+mod)%mod;
 33         }
 34         for(int i=(pos[r]-1)*m+1;i<=r;i++)
 35             a[i]=(a[i]+c+mod)%mod;
 36         mul[pos[r]]=1;add[pos[r]]=0;
 37     }
 38 }
 39 
 40 void update_mul(int l,int r,int c)
 41 {
 42     if(pos[l]==pos[r]){
 43         for(int i=(pos[l]-1)*m+1;i<=pos[l]*m;i++){
 44             a[i]=(a[i]*mul[pos[l]]%mod+add[pos[l]]+mod)%mod;
 45         }
 46         for(int i=l;i<=r;i++)
 47             a[i]=(a[i]*c+mod)%mod;
 48         mul[pos[l]]=1;add[pos[l]]=0;
 49     }
 50     else{
 51         for(int i=(pos[l]-1)*m+1;i<=pos[l]*m;i++){
 52             a[i]=(a[i]*mul[pos[l]]%mod+add[pos[l]]+mod)%mod;
 53         }
 54         for(int i=l;i<=pos[l]*m;i++)
 55             a[i]=(a[i]*c+mod)%mod;
 56         mul[pos[l]]=1;add[pos[l]]=0;
 57         for(int i=pos[l]+1;i<pos[r];i++){
 58             add[i]=(add[i]*c+mod)%mod;
 59             mul[i]=(mul[i]*c+mod)%mod;
 60         }
 61         for(int i=(pos[r]-1)*m+1;i<=min(pos[r]*m,n);i++){
 62             a[i]=(a[i]*mul[pos[r]]%mod+add[pos[r]]+mod)%mod;
 63         }
 64         for(int i=(pos[r]-1)*m+1;i<=r;i++)
 65             a[i]=(a[i]*c+mod)%mod;
 66         mul[pos[r]]=1;add[pos[r]]=0;
 67     }
 68 }
 69 
 70 int main()
 71 {
 72     scanf("%d",&n);
 73     m=sqrt(n);
 74     for(int i=1;i<=n;i++){
 75         scanf("%d",&a[i]);
 76         a[i]%=mod;
 77         pos[i]=(i-1)/m+1;
 78         mul[pos[i]]=1;
 79         add[pos[i]]=0;
 80     }
 81     for(int i=1;i<=n;i++){
 82         int op,l,r,c;
 83         scanf("%d%d%d%d",&op,&l,&r,&c);
 84         c%=mod;
 85         if(op==0){
 86             update_add(l,r,c);
 87         }
 88         else if(op==1){
 89             update_mul(l,r,c);
 90         }
 91         else if(op==2){
 92             printf("%d
",(a[r]*mul[pos[r]]+add[pos[r]])%mod);
 93         }
 94     }
 95 }
 96 
 97 
 98 /*
 99 10
100 1 3 4 2 5 7 11 3 5 1
101 0 1 5 1
102 1 1 7 2
103 2 3 9 1
104 0 4 8 1
105 1 1 5 2
106 1 3 5 2
107 2 5 7 1
108 1 3 5 2
109 2 2 3 2
110 2 3 4 5
111 
112 5
113 23
114 80
115 56
116 */

LOJ #6283. 数列分块入门 7-分块(区间乘法、区间加法、单点查询)

#6283. 数列分块入门 7

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示