题目：Least common multiple
链接：http://acm.hdu.edu.cn/showproblem.php?pid=4913
题意：有一个集合s，包含x1,x2,...,xn，有xi=2^ai * 3^bi，然后给你a数组和b数组，求s所有子集合的最小公倍数之和。比如S={18,12,18}，那么有{18}，{12}，{18}，{18,12}，{18,18}，{12,18}，{18,12,18}，所以答案是174。
思路：
1. 最小公倍数，因为xi只包含两个质因子2、3，那么子集合的最小公倍数其实就是2^max(a[]) * 3^max(b[])。max(a[])就是子集合相关的a数组集合中最大的ai。
2. 先简化题目，如果题目中的xi = 2^ai，那么可以对x数组进行从小到大排序。那么 lcm(x0,x1,...,xi)=xi，又 i 前面包含xi的子集合数量为2^(i-1)（其实就是xj(j<i)放入集合为1，不放入集合为0），那么最后的答案为 ∑ (2^ i-1 ) * xi，也就是ans[i]=ans[i-1]+2^(i-1)*2^(ai)
3. 回归题目，题目中多了b数组，那么我们可以按b排序，令 x= i 前面 a的值小于ai的数量，令p1、p2、...、pk为i 前面 a的值比ai大的 位置。那么ans[i] = ans[i-1] + ( 2^x * 2^ai + 2^x * 2^ap1 + 2^(x+1) * 2^ap2 + ... + 2^(x+k-1) * 2^apk ) * 3^bi。
3中的递推公式可以如下理解：
推到i 就表示i 必选，那么i 前面最小公倍数为2^ai * 3^bi 的有 2^x 个，就是 x 个 a的值比ai小的xj 选与不选的问题了。比ai大的不选（因为选了的话，最小公倍数就不是xi了）
然后xp1必选，也就是 第一个a的值比ai大的 xj必选，又 xi 必选，剩下x个比ai小的可选可不选，有2^x种情况，这2^x种情况的最小公倍数为2^ap1 * 3^bi。
再接着xp2必选（注意：xi 还是必选，但xp1可选可不选），有2^(x+1)种情况，他们的最小公倍数为2^ap2 * 3^bi。
。。。
上面的递推公式只是告知ans[i]的算法，当然不能直接照样计算，因为即使你可以很容易得到 i 前面a值比ai大的位置，最坏情况下（b递增，a递减），时间复杂度也高达O(n*n)。
现在我们可以维护2^x * 2^aj（其实就是维护那个x值），我们建一个线段树（离散型的），孩子结点（i,i）对应a值排名为i 的xj（x数组是按b排序的），线段树的结点包含sum、cnt和mulCnt三个属性，当遍历（从1-n）到j 时，xj对应的a值排名i的线段树结点cnt置1，sum置为2^x * 2^aj，然后向上更新，现在如果问x值，就可以用线段树很快地得出来。就是1-i 中cnt已经是1的数量。而2^x * 2^ap1 + 2^(x+1) * 2^ap2 + ... + 2^(x+k-1) * 2^apk可以通过维护得到，就是说每次计算完，从i+1到n的已经置为1（就是前面已经出现过的）的sum值乘2（因为比他们小的又多了一个aj，就是x+1）。
AC代码：
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define Mod 1000000007
using namespace std;
typedef long long LL; LL qpow(LL a,LL b)
{
LL ret=;
while(b)
{
if(b&) ret=ret*a%Mod;
a=a*a%Mod;
b>>=;
}
return ret;
} struct X
{
int id;
int a,b;
int ra; //a的排名
};
bool cmp1(X a,X b) //根据a排序
{
return a.a<b.a;
}
bool cmp2(X a,X b) //根据b排序
{
return a.b<b.b;
} X x[]; struct Node
{
LL sum,cnt;
LL mulCnt; //该区间乘了多少个2
int l,r;
int mid()
{
return (l+r)/;
}
};
Node v[];
void build(int l,int r,int rt)
{
v[rt].sum=v[rt].cnt=;
v[rt].mulCnt=;
v[rt].l=l;
v[rt].r=r;
if(l==r) return ;
build(l,v[rt].mid(),rt<<);
build(v[rt].mid()+,r,rt<<|);
} void push_down(int rt,bool flag)
{
if(v[rt].l==v[rt].r)
{
v[rt].mulCnt=;
return ;
}
v[rt<<].mulCnt+=v[rt].mulCnt;
v[rt<<|].mulCnt+=v[rt].mulCnt;
if(flag==)
{
v[rt<<].sum=v[rt<<].sum*qpow(,v[rt<<].mulCnt)%Mod;
push_down(rt<<,);
v[rt<<|].sum=v[rt<<|].sum*qpow(,v[rt<<|].mulCnt)%Mod;
push_down(rt<<|,);
}
v[rt].mulCnt=;
} LL look_cnt(int l,int r,int rt)
{
if(l==v[rt].l&&r==v[rt].r) return v[rt].cnt;
int mid=v[rt].mid();
if(l>mid) return look_cnt(l,r,rt<<|);
else if(r<=mid) return look_cnt(l,r,rt<<);
else return look_cnt(l,mid,rt<<)+look_cnt(mid+,r,rt<<|);
} LL look_sum(int l,int r,int rt)
{
if(l==v[rt].l&&r==v[rt].r)
{
v[rt].sum=v[rt].sum*qpow(2LL,v[rt].mulCnt)%Mod;
push_down(rt,);
return v[rt].sum;
}
push_down(rt,);
int mid=v[rt].mid();
LL ret;
if(l>mid) ret=look_sum(l,r,rt<<|);
else if(r<=mid) ret=look_sum(l,r,rt<<);
else ret=(look_sum(l,mid,rt<<)+look_sum(mid+,r,rt<<|))%Mod;
v[rt].sum=(v[rt<<].sum+v[rt<<|].sum)%Mod;
return ret;
} void update(int ra,int a,int rt)
{
if(v[rt].l==v[rt].r)
{
v[rt].cnt=;
LL x = ra== ? :look_cnt(,ra-,); //x 就是在a的前面（按b排序后）排名比a小的数量
v[rt].sum=qpow(,x+a);
v[rt].mulCnt=;
return ;
}
push_down(rt,);
if(ra<=v[rt].mid())
update(ra,a,rt<<);
else update(ra,a,rt<<|);
v[rt].cnt=v[rt<<].cnt+v[rt<<|].cnt;
v[rt].sum=(v[rt<<].sum+v[rt<<|].sum)%Mod;
} void mul(int l,int r,int rt)
{
if(v[rt].l==l&&v[rt].r==r)
{
v[rt].mulCnt++;
v[rt].sum=v[rt].sum*qpow(2LL,v[rt].mulCnt)%Mod;
push_down(rt,);
return ;
}
push_down(rt,);
if(r<=v[rt].mid()) mul(l,r,rt<<);
else if(l>v[rt].mid()) mul(l,r,rt<<|);
else
{
mul(l,v[rt].mid(),rt<<);
mul(v[rt].mid()+,r,rt<<|);
}
v[rt].sum=(v[rt<<].sum+v[rt<<|].sum)%Mod;
} int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
build(,n-,);
for(int i=;i<n;i++)
{
scanf("%d%d",&x[i].a,&x[i].b);
x[i].id=i;
}
sort(x,x+n,cmp1);
for(int i=;i<n;i++) x[i].ra=i;
sort(x,x+n,cmp2);
LL ans=;
for(int i=;i<n;i++)
{
update(x[i].ra,x[i].a,);
ans = (ans + look_sum(x[i].ra,n-,)*qpow(3LL,x[i].b))%Mod;
if(x[i].ra!=n-) mul(x[i].ra+,n-,);
}
printf("%I64d\n",ans);
}
return ;
}