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=;

il int gi()

{

    int a=;char x=getchar();bool f=;

    while((x<''||x>'')&&x!='-')x=getchar();

    if(x=='-')x=getchar(),f=;

    while(x>=''&&x<='')a=a*+x-,x=getchar();

    return f?-a:a;

}

ll a[N],n,m,tot[N];

int main()

{

    n=gi(),m=gi();

    for(int i=;i<=n;i++)a[i]=gi();

    int k,x,y;

    while(m--){

        scanf("%lld",&k);

        if(k==){x=gi();

            ll ans=;

            for(int i=;i*i<=x;i++)

            if(x%i==){i*i==x?ans+=tot[i]:ans+=tot[i]+tot[x/i];}

            printf("%lld\n",a[x]+ans);

        }

        else {

            x=gi();y=gi();tot[x]+=y;

        }

    }

    return ;

}