思路:
(1)对于每一个可能的因子(2..100万),记录是其倍数的所有数的下标,对于某个询问[l,r,v],找出l,r中所有为v倍数的数,除掉就好了。
(2)维护一个树状数组,修改值以及统计区间和。
这样仍然会超时,加了个优化,(1)中这些因子如果没在询问1中的v出现过(而v最多有10万个不同的),就不用记录。这样可以过所有数据。
#include<string.h> #include<stdlib.h> #include<vector> #include<stdio.h> #include<set> #include<iostream> #include<algorithm> using namespace std; #define N 1010000 set<int> s[N]; int a[N/10]; long long c[N/10]; int n,m; int lowbit(int x){return x&-x;} long long bit_sum(int k){ long long ret=0; while (k){ ret+=c[k]; k-=lowbit(k); } return ret; } long long bit_sum(int l,int r){ return bit_sum(r)-bit_sum(l-1); } int bit_set(int k,int v){ int tmp=v-a[k]; a[k]=v; while (k<=n){ c[k]+=tmp; k+=lowbit(k); } return 0; } int div(int l,int r,int v){ set<int>::iterator it=s[v].lower_bound(l); while (it!=s[v].end() && *it<=r){ int idx=*it; if (a[idx]%v==0){ bit_set(idx,a[idx]/v); } it++; if (a[idx]%v!=0) s[v].erase(idx); } return 0; } int op[N/10],l[N/10],r[N/10],v[N/10]; bool existV[N]; int read(){ //getp(); memset(c,0,sizeof(c)); scanf("%d%d",&n,&m); for (int i=1;i<=n;i++){ int tmp; scanf("%d",&tmp); bit_set(i,tmp); } memset(existV,0,sizeof(existV)); for (int i=1;i<=m;i++){ scanf("%d%d%d",&op[i],&l[i],&r[i]); if (op[i]==1) {scanf("%d",&v[i]);existV[v[i]]=true;} } //for (int i=1;i<N;i++) if (existV[i]) printf("%d ",i) ;putchar('\n'); for (int i=1;i<=n;i++){ int tmp=a[i]; for (int j=1;j*j<=tmp;j++){ int p=tmp/j; if (j*p!=tmp)continue; //j*p=tmp && j<=p if (j!=1 && existV[j])s[j].insert(i); if (p!=j && existV[p])s[p].insert(i); } } return 0; } int main(){ read(); for (int i=1;i<=m;i++){ if (op[i]==1){ div(l[i],r[i],v[i]); }else{ cout<<bit_sum(l[i],r[i])<<endl; } } return 0; }