hdu4911
max(逆序数-k，0）
#include <iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<stack>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
#define LL long long
#define gcd(a,b) (b==0?a:gcd(b,a%b))
#define lcm(a,b) (a*b/gcd(a,b))
//O（n）求素数，1-n的欧拉数
#define N 100010
//A^x = A^(x % Phi(C) + Phi(C)) (mod C)
map<int,int>f;
struct node
{
int a;
int id;
}p[N];
int s[N<<],b[N];
void up(int w)
{
s[w] = s[w<<]+s[w<<|];
}
void build(int l,int r,int w)
{
if(l==r)
{
s[w] = ;
return ;
}
int m = (l+r)>>;
build(l,m,w<<);
build(m+,r,w<<|);
up(w);
}
void update(int p,int d,int l,int r,int w)
{
if(l==r)
{
s[w] += d;
return ;
}
int m =(l+r)>>;
if(p<=m)
update(p,d,l,m,w<<);
else
update(p,d,m+,r,w<<|);
up(w); }
int query(int a,int b,int l,int r,int w)
{
if(a<=l&&b>=r)
return s[w];
int m = (l+r)>>;
int res = ;
if(a<=m) res+=query(a,b,l,m,w<<);
if(b>m) res+=query(a,b,m+,r,w<<|);
return res;
}
bool cmp(node a,node b)
{
return a.a<b.a;
}
int main()
{
int n,i,j,k;
while(scanf("%d%d",&n,&k)!=EOF)
{
f.clear();
for(i = ; i<= n; i++)
{
scanf("%d",&p[i].a);
p[i].id = i;
b[i] = p[i].a;
}
sort(b+,b+n+);
f[b[]] = ;
int o = ;
for(i = ; i<= n; i++)
if(b[i]!=b[i-])
{
f[b[i]] = ++o;
}
build(,o,);
LL s = ;
for(i = ; i<= n ;i++)
{
//cout<<f[p[i].a]<<endl;
int kk = ;
if(f[p[i].a]<o)
kk = query(f[p[i].a]+,o,,o,);
update(f[p[i].a],,,o,);
s+=kk;
}
LL x = ;
s = max(x,s-k);
cout<<s<<endl;
}
return ;
}
HDU4913
几个数的LCM = 分解质因子之后每个质因子的最高次幂相乘之积 这里因为只有2、3 . lcm = 2^max*3^max
可以把b从小到大排序
x1 a1 b1
x2 a2 b2
x3 a3 b3
x4 a4 b4
假如现在集合里面没有数为空集，从上往下依次插入这些数，插入x1时 ，因为当前b1是最大的，它所构成的所有集合中3的最高次幂肯定选b1，
所以现在只需找到集合中的2的最高次幂分别有哪些，显然第一个只有 a1.而当插入第二个、第三个、第四个时，3的最高次幂分别为b2 b3 b4 ，a的选择会有多种，
对于如果选择了a1那么这样的集合将会有2^k个，k = 比a1小的数的个数，总的式子为 bi(2^k1*2^a1+2^k2*2^a2+2^k3*2^a3......) ( 所有的aj<ai)
这样可以开一个线段树维护前面有多少个比ai小的数，再开一个线段树维护后面的每一项的总值，例如1就为2^k1*2^a1
每插入一项，就把2^ki*2^ai放入第i个位置，求完当前和值后，将所有大于ai的值*2，依次扫描一遍就可得出结果。
#include <iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<stack>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
#define LL __int64
#define gcd(a,b) (b==0?a:gcd(b,a%b))
#define lcm(a,b) (a*b/gcd(a,b))
#define N 100005
#define mod 1000000007
struct node
{
int a,b;
int id;
} p[N];
LL lz[N<<],s[N<<];
LL sum[N<<];
int po[N];
LL mul(LL a,LL b,LL m)
{
LL d,t;
d=;
t=a;
while (b>)
{
if (b%==)
d=(d*t)%m;
b/=;
t=(t*t)%m;
}
return d;
}
bool cmp(node x,node y)
{
return x.a<y.a;
}
bool cmpp(node x,node y)
{
return x.b<y.b;
}
void up(int w)
{
s[w] = (s[w<<]+s[w<<|])%mod;
}
void build(int l,int r,int w)
{
lz[w] = ;
if(l==r)
{
s[w] = ;
return ;
}
int m = (l+r)>>;
build(l,m,w<<);
build(m+,r,w<<|);
up(w);
}
void down(int w,int m)
{
if(lz[w]!=)
{
lz[w<<] = (lz[w<<]*lz[w])%mod;
lz[w<<|] = (lz[w<<|]*lz[w])%mod;
s[w<<] = (s[w<<]*lz[w])%mod;
s[w<<|] = (s[w<<|]*lz[w])%mod;
lz[w] = ;
}
}
void update(int p,LL d,int l,int r,int w)
{
if(l==r)
{
s[w] = d;
return ;
}
down(w,r-l+);
int m = (l+r)>>;
if(p<=m)
update(p,d,l,m,w<<);
else
update(p,d,m+,r,w<<|);
up(w);
}
void update1(int a,int b,LL d,int l,int r,int w)
{
if(a<=l&&b>=r)
{
s[w] = (s[w]*d)%mod;
lz[w] = (lz[w]*d)%mod;
return ;
}
down(w,r-l+);
int m = (l+r)>>;
if(a<=m) update1(a,b,d,l,m,w<<);
if(b>m) update1(a,b,d,m+,r,w<<|);
up(w);
}
LL query(int a,int b,int l,int r,int w)
{
if(a<=l&&b>=r) return s[w];
int m = (l+r)>>;
LL res = ;
if(a<=m) res+=query(a,b,l,m,w<<);
if(b>m) res = (res+query(a,b,m+,r,w<<|))%mod;
return res;
}
void up1(int w)
{
sum[w] = sum[w<<]+sum[w<<|];
}
void build1(int l,int r,int w)
{
if(l==r)
{
sum[l] = ;
return ;
}
int m = (l+r)>>;
build1(l,m,w<<);
build1(m+,r,w<<|);
up1(w);
}
void update2(int p,int l,int r,int w)
{
if(l==r)
{
sum[w] = ;
return ;
}
int m = (l+r)>>;
if(p<=m)
update2(p,l,m,w<<);
else update2(p,m+,r,w<<|);
up1(w);
}
int query1(int a,int b,int l,int r,int w)
{
if(a<=l&&b>=r)
{
return sum[w];
}
int m = (l+r)>>;
int res=;
if(a<=m) res+=query1(a,b,l,m,w<<);
if(b>m) res+=query1(a,b,m+,r,w<<|);
return res;
}
int main()
{
int n,i;
while(scanf("%d",&n)!=EOF)
{
memset(sum,,sizeof(sum));
for(i = ; i<= n; i++)
{
scanf("%d%d",&p[i].a,&p[i].b);
p[i].id = i;
}
sort(p+,p+n+,cmp);
for(i = ; i <= n ; i++)
{
po[p[i].id] = i;
}
sort(p+,p+n+,cmpp);
build(,n,);
LL ans = ;
build1(,n,);
for(i = ; i <= n; i++)
{
int k = query1(,po[p[i].id],,n,);
//cout<<k<<" "<<p[i].a<<" "<<po[p[i].id]<<endl;
update2(po[p[i].id],,n,);
update(po[p[i].id],mul(,p[i].a+k,mod),,n,);
LL ss = query(po[p[i].id],n,,n,);
// cout<<ss<<endl;
ans=(ans+(mul(,p[i].b,mod)*ss)%mod)%mod;
if(po[p[i].id]<n)
update1(po[p[i].id]+,n,,,n,);
}
printf("%I64d\n",ans);
}
return ;
}
#include <iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<stack>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
#define LL __int64
#define gcd(a,b) (b==0?a:gcd(b,a%b))
#define lcm(a,b) (a*b/gcd(a,b))
#define N 100005
#define mod 1000000007
struct node
{
int a,b;
int id;
} p[N];
LL lz[N<<],s[N<<];
LL sum[N<<];
int po[N];
LL mul(LL a,LL b,LL m)
{
LL d,t;
d=;
t=a;
while (b>)
{
if (b%==)
d=(d*t)%m;
b/=;
t=(t*t)%m;
}
return d;
}
bool cmp(node x,node y)
{
return x.a<y.a;
}
bool cmpp(node x,node y)
{
return x.b<y.b;
}
void up(int w)
{
s[w] = (s[w<<]+s[w<<|])%mod;
}
void build(int l,int r,int w)
{
lz[w] = ;
if(l==r)
{
s[w] = ;
return ;
}
int m = (l+r)>>;
build(l,m,w<<);
build(m+,r,w<<|);
up(w);
}
void down(int w,int m)
{
if(lz[w]!=)
{
lz[w<<] = (lz[w<<]*lz[w])%mod;
lz[w<<|] = (lz[w<<|]*lz[w])%mod;
s[w<<] = (s[w<<]*lz[w])%mod;
s[w<<|] = (s[w<<|]*lz[w])%mod;
lz[w] = ;
}
}
void update(int p,LL d,int l,int r,int w)
{
if(l==r)
{
s[w] = d;
return ;
}
down(w,r-l+);
int m = (l+r)>>;
if(p<=m)
update(p,d,l,m,w<<);
else
update(p,d,m+,r,w<<|);
up(w);
}
void update1(int a,int b,LL d,int l,int r,int w)
{
if(a<=l&&b>=r)
{
s[w] = (s[w]*d)%mod;
lz[w] = (lz[w]*d)%mod;
return ;
}
down(w,r-l+);
int m = (l+r)>>;
if(a<=m) update1(a,b,d,l,m,w<<);
if(b>m) update1(a,b,d,m+,r,w<<|);
up(w);
}
LL query(int a,int b,int l,int r,int w)
{
if(a<=l&&b>=r) return s[w];
int m = (l+r)>>;
LL res = ;
if(a<=m) res+=query(a,b,l,m,w<<);
if(b>m) res = (res+query(a,b,m+,r,w<<|))%mod;
return res;
}
void up1(int w)
{
sum[w] = sum[w<<]+sum[w<<|];
}
void build1(int l,int r,int w)
{
if(l==r)
{
sum[l] = ;
return ;
}
int m = (l+r)>>;
build1(l,m,w<<);
build1(m+,r,w<<|);
up1(w);
}
void update2(int p,int l,int r,int w)
{
if(l==r)
{
sum[w] = ;
return ;
}
int m = (l+r)>>;
if(p<=m)
update2(p,l,m,w<<);
else update2(p,m+,r,w<<|);
up1(w);
}
int query1(int a,int b,int l,int r,int w)
{
if(a<=l&&b>=r)
{
return sum[w];
}
int m = (l+r)>>;
int res=;
if(a<=m) res+=query1(a,b,l,m,w<<);
if(b>m) res+=query1(a,b,m+,r,w<<|);
return res;
}
int main()
{
int n,i;
while(scanf("%d",&n)!=EOF)
{
memset(sum,,sizeof(sum));
for(i = ; i<= n; i++)
{
scanf("%d%d",&p[i].a,&p[i].b);
p[i].id = i;
}
sort(p+,p+n+,cmp);
for(i = ; i <= n ; i++)
{
po[p[i].id] = i;
}
sort(p+,p+n+,cmpp);
build(,n,);
LL ans = ;
build1(,n,);
for(i = ; i <= n; i++)
{
int k = query1(,po[p[i].id],,n,);
//cout<<k<<" "<<p[i].a<<" "<<po[p[i].id]<<endl;
update2(po[p[i].id],,n,);
update(po[p[i].id],mul(,p[i].a+k,mod),,n,);
LL ss = query(po[p[i].id],n,,n,);
// cout<<ss<<endl;
ans=(ans+(mul(,p[i].b,mod)*ss)%mod)%mod;
if(po[p[i].id]<n)
update1(po[p[i].id]+,n,,,n,);
}
printf("%I64d\n",ans);
}
return ;
}