桃花村 题解(思维+数学)

题目链接

题目思路

这个题目真的挺有意思的

任意取一个坐标设他的(A_i)为(a)和(abs(i-x))为(dis)

则显然若在(h)时刻的燃烧程度为(t)则要满足

(a imes (h-dis)=t)

则显然(t)为(a)的倍数

而你如果知道t可以枚举(a)，那么你也知道(h)，则(dis)值你也知道

把所有(t)相同的操作储存起来，最后一起操作

顺便注意(t=0)的情况要特判

代码是借鉴rank前几的很简单

复杂度就是一个调和级数

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n,m,x;
int a[maxn];
int opt[maxn],h[maxn],t[maxn];
int ans[maxn];
unordered_map<int,int> mp[maxn];
vector<pair<int,int> > vec[maxn];
int num[maxn];
signed main(){
    scanf("%d%d%d",&n,&m,&x);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        int dis=abs(i-x);
        num[dis]++;
        mp[dis][a[i]]++;
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&opt[i],&h[i]);
        if(opt[i]==1){
            scanf("%d",&t[i]);
            vec[t[i]].push_back({i,h[i]});
        }
    }
    for(int i=1;i<=1e6;i++){
        for(int j=i;j<=1e6;j+=i){//枚举t[i]
            int a=j/i;
            for(auto k:vec[j]){
                int dis=k.se-a;
                if(dis<0) continue;
                if(mp[dis].count(i)){
                    ans[k.fi]+=mp[dis][i];
                }
            }
        }
    }
    ll pr=0;
    for(int i=1;i<=m;i++){
        if(opt[i]==1){
            if(t[i]==0){
                pr+=num[h[i]];
            }else{
                pr+=ans[i];
            }
        }else{
            printf("%lld
",pr);
        }
    }
    return 0;
}