rt,没有写奇怪的内存池还是什么优化
最好的一次记录:4 * TLE,最慢 504ms
Code:
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
typedef long long ll;
const int maxn = 5e5 + 1;
const int max_size = 1.5e7 + 1;
static char buf[1000000],*p1=buf,*p2=buf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
inline int Read(){
register int x = 0;
register char c = getchar();
for(;c < '0' || c > '9';c = getchar());
for(;c >= '0' && c <= '9';c = getchar()) x = x * 10 + (c ^ '0');
return x;
}
int n,m,k;
std::vector<int> value[maxn];
int a[maxn],tmp[maxn],len = 0,lc[max_size],rc[max_size],id[max_size],heap[max_size],siz[max_size],cnt = 0,rt[maxn];
inline int new_node(int i){
siz[++cnt] = 1;
id[cnt] = i;
heap[cnt] = rand();
return cnt;
}
inline int build(int l,int r){
if(l > r) return 0;
int mid = l + r >> 1,i = new_node(tmp[mid]);
lc[i] = build(l,mid - 1);
rc[i] = build(mid + 1,r);
siz[i] = 1 + siz[lc[i]] + siz[rc[i]];
return i;
}
inline int merge(int x,int y){
if(!x || !y) return x + y;
if(heap[x] < heap[y]){
rc[x] = merge(rc[x],y);
siz[x] = 1 + siz[lc[x]] + siz[rc[x]];
return x;
} else {
lc[y] = merge(x,lc[y]);
siz[y] = 1 + siz[lc[y]] + siz[rc[y]];
return y;
}
}
inline void split(int i,int k,int& x,int& y){
if(!i) x = y = 0;
else {
if(id[i] <= k){
x = i;
split(rc[i],k,rc[i],y);
} else {
y = i;
split(lc[i],k,x,lc[i]);
}
siz[i] = 1 + siz[lc[i]] + siz[rc[i]];
}
}
ll T[maxn];
inline void update(int i,ll x){
for(;i <= n;i += (i & -i)) T[i] += x;
}
inline ll query(int i){
ll ret = 0;
for(;i;i -= (i & -i)) ret += T[i];
return ret;
}
inline void dfs(int p,int x){
if(!p) return;
if(lc[p]) dfs(lc[p],x);
if(a[id[p]] % x == 0){
update(id[p],-a[id[p]]);
a[id[p]] /= x;
update(id[p],a[id[p]]);
}
if(a[id[p]] % x == 0)
tmp[++len] = id[p];
if(rc[p]) dfs(rc[p],x);
}
inline void update(int l,int r,int a){
int x,y,z;
split(rt[a],r,x,z);
split(x,l - 1,x,y);
len = 0;
dfs(y,a);
int k = build(1,len);
rt[a] = merge(merge(x,k),z);
}
signed main(){
n = Read(),m = Read();
for(register int i = 1;i <= n;++i){
a[i] = Read();
update(i,a[i]);
k = sqrt(a[i]);
for(register int j = 1;j <= k;++j)
if(a[i] % j == 0){
value[j].push_back(i);
if(j * j != a[i]) value[a[i] / j].push_back(i);
}
}
for(register int i = 1;i < maxn;++i){
len = 0;
for(int j = 0;j < value[i].size();++j) tmp[++len] = value[i][j];
rt[i] = build(1,len);
}
ll last = 0;
register int opt,l,r,x;
while(m--){
opt = Read();
l = Read() ^ last;
r = Read() ^ last;
if(opt == 1){
x = Read() ^ last;
if(x != 1) update(l,r,x);
} else printf("%lld\n",last = query(r) - query(l - 1));
}
return 0;
}
感觉自己像马牛逼!!!