P1483 序列变换

题目描述

给定一个由n个整数构成的序列，你需要对它进行如下操作：

操作1：输入格式“1 x y”，表示把所有a[kx]（k为正整数，kx<=n）都加上y。

操作2：输入格式“2 j”，表示输出a[j]。

输入输出格式

输入格式：

 

第一行，两个数n,m，表示有n个数，m条操作。

第二行，n个数a[1],a[2],…,a[n]。

接下来m行，为m条操作。

 

输出格式：

 

输出若干行，每行对应一次操作2。

 

输入输出样例

输入样例#1： 

5 4
6 9 9 8 1 
2 4
1 2 5
1 3 1
2 4

输出样例#1： 

8
13

说明

对于40%的数据，n<=100

对于100%的数据，n<=1000000，m<=100000，|a[i]|<=1000000，|y|<=1000000，x<=n，j<=n，操作2不超过10000条。

 

Solution:

本题不需要什么特别厉害的数据结构。我们直接进行模拟，对于1操作，统计一下那些数的倍数被修改，当2操作查询时直接开根枚举因子并修改，唯一要注意的是当i*i==x时只要加1次，其它的话两个因子都要累加。可以算一波复杂度：O(m√n)，因为最多查询10000次，而数最大为1000000,所以最坏情况也就10⁷

代码：

#include<bits/stdc++.h>
#define il inline
#define ll long long
using namespace std;
const int N=1000005;
il int gi()
{
    int a=0;char x=getchar();bool f=0;
    while((x<'0'||x>'9')&&x!='-')x=getchar();
    if(x=='-')x=getchar(),f=1;
    while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();
    return f?-a:a;
}
ll a[N],n,m,tot[N];
int main()
{
    n=gi(),m=gi();
    for(int i=1;i<=n;i++)a[i]=gi();
    int k,x,y;
    while(m--){
        scanf("%lld",&k);
        if(k==2){x=gi();
            ll ans=0;
            for(int i=1;i*i<=x;i++)
            if(x%i==0){i*i==x?ans+=tot[i]:ans+=tot[i]+tot[x/i];}
            printf("%lld
",a[x]+ans);
        }
        else {
            x=gi();y=gi();tot[x]+=y;
        }
    }
    return 0;
}