题目描述
atm参加了速算训练班，经过刻苦修炼，对以2为底的对数算得飞快，人称Log大侠。 一天，Log大侠的好友 drd 有一些整数序列需要变换，Log大侠正好施展法力... 变换的规则是： 对其某个子序列的每个整数变为: [log_2 (x) + 1] 其中 [] 表示向下取整，就是对每个数字求以2为底的对数，然后取下整。 例如对序列 3 4 2 操作一次后，这个序列会变成 2 3 2。 drd需要知道，每次这样操作后，序列的和是多少。 【输入格式】 第一行两个正整数 n m 。 第二行 n 个数，表示整数序列，都是正数。 接下来 m 行，每行两个数 L R 表示 atm 这次操作的是区间 [L, R]，数列序号从1开始。 【输出格式】 输出 m 行，依次表示 atm 每做完一个操作后，整个序列的和。 例如，输入： 3 3 5 6 4 1 2 2 3 1 3 程序应该输出： 10 8 6 【数据范围】 对于 30% 的数据， n, m <= 10^3 对于 100% 的数据， n, m <= 10^5 资源约定： 峰值内存消耗 < 256M CPU消耗 < 1000ms
题解：首先一个数若为1或2就会不变了，所以1e9的数取log最多取30就不变了，直接线段树维护区间和，每次更新直接更新到节点即可，复杂度30*n*log(n)，或者并查集维护下，该位置已经到1或2了，就指向下一个，跳过当前位置，或者用set维护一下，若一个数变为1或2，就直接在set中删除，这里注意，不知直接在set里面改变，要先删除，然后把改变后的再插入。
线段树：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; struct node{ int l,r; ll sum; int x; int flag; }tree[N<<2]; int n,m; void pushup(int cur) { tree[cur].sum=tree[cur<<1].sum+tree[cur<<1|1].sum; tree[cur].flag=tree[cur<<1].flag&&tree[cur<<1|1].flag; } void build(int l,int r,int cur) { tree[cur].l=l; tree[cur].r=r; tree[cur].flag=0; if(l==r) { scanf("%d",&tree[cur].x); tree[cur].sum=tree[cur].x; if(tree[cur].x<=2) tree[cur].flag=1; return; } int mid=(r+l)>>1; build(l,mid,cur<<1); build(mid+1,r,cur<<1|1); pushup(cur); } void update(int pl,int pr,int cur) { if(tree[cur].flag)return; if(tree[cur].l==tree[cur].r) { tree[cur].x=(int)log2(tree[cur].x*1.0)+1; tree[cur].sum=tree[cur].x; if(tree[cur].sum<=2) tree[cur].flag=1; return; } if(pl<=tree[cur<<1].r) update(pl,pr,cur<<1); if(pr>=tree[cur<<1|1].l) update(pl,pr,cur<<1|1); pushup(cur); } int main() { scanf("%d%d",&n,&m); build(1,n,1); int l,r; while(m--) { scanf("%d%d",&l,&r); update(l,r,1); printf("%lld\n",tree[1].sum); } return 0; }并查集：
#include<iostream> #include<cstdio> #include<set> #include<cmath> using namespace std; typedef long long ll; const int N=1e5+10; int n,m,a[N],f[N]; int fath(int x) { return x==f[x]?f[x]:f[x]=fath(f[x]); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n+1;i++) f[i]=i; ll ans=0; for(int i=1;i<=n;i++)scanf("%d",&a[i]),ans+=a[i]; int l, r; while(m--) { scanf("%d%d",&l,&r); for(int i=l;i<=r;i=fath(i)) { ans-=a[i]; a[i]=(int)log2(a[i])+1; ans+=a[i]; if(a[i]<=2) { f[i]=f[i+1]; } else i++; } printf("%lld\n",ans); } return 0; }set：
#include<iostream> #include<cstdio> #include<set> #include<cmath> using namespace std; typedef long long ll; int n,m; set<pair<int,int> > s; set<pair<int,int> >::iterator posl,posr; int main() { int x; ll ans=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&x); s.insert(make_pair(i,x)); ans+=x; } s.insert(make_pair(n+1,1)); int l,r; pair<int,int> tmp(0,0); while(m--) { scanf("%d%d",&l,&r); posl=s.lower_bound(make_pair(l,0)); posr=s.upper_bound(make_pair(r+1,0)); while(posl!=posr) { tmp=*posl; posl++; s.erase(tmp); ans-=tmp.second; tmp.second=(int)log2(tmp.second)+1; ans+=tmp.second; if(tmp.second>2) s.insert(tmp); } printf("%lld\n",ans); } return 0; }
