首页 > 代码库 > 玲珑学院OJ 1023 - Magic boy Bi Luo with his excited math problem 树状数组暴力
玲珑学院OJ 1023 - Magic boy Bi Luo with his excited math problem 树状数组暴力
分析：a^b+2(a&b)=a+b so->a^(-b)+2(a&(-b))=a-b
然后树状数组分类讨论即可
链接：http://www.ifrog.cc/acm/problem/1023
吐槽：这个题本来是mod(2^40)，明显要用快速乘啊，但是用了以后狂T，不用反而过了，不懂出题人
#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <string>#include <cstdio>#include <cstring>using namespace std;typedef long long LL;const int N = 1e5+5;const LL mod = (1ll<<40);int T,n,m,a[N],b[N],p[N],cnt,kase;LL c[4][N],sum[4];inline void init(){ for(int i=0; i<4; ++i) for(int j=0;j<=cnt;++j)c[i][j]=0; sum[0]=sum[1]=sum[2]=sum[3]=0;}inline void up(LL &x,LL t){ x+=t; if(x>=mod)x-=mod;}inline void add(int pos,int x,LL t){ for(int i=x; i<=cnt; i+=i&(-i))up(c[pos][i],t);}inline LL ask(int pos,int x){ LL ret=0; for(int i=x; i; i-=i&(-i))up(ret,c[pos][i]); return ret;}LL ksc(LL x,LL y){ LL ret=0; while(y) { if(y&1)up(ret,x); y>>=1; up(x,x); } return ret;}int main(){ scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=1; i<=n; ++i)scanf("%d",&a[i]); for(int i=1; i<=m; ++i)scanf("%d",&b[i]),p[i]=b[i]; sort(p+1,p+1+m); cnt = unique(p+1,p+1+m)-p-1; int ptr=1; LL ret=0; init(); for(int i=1; i<=n; ++i) { int pos; for(; ptr<=m&&ptr<i; ++ptr) { pos = lower_bound(p+1,p+1+cnt,b[ptr])-p; add(0,pos,1);++sum[0]; add(1,pos,ptr);up(sum[1],ptr); add(2,pos,b[ptr]);up(sum[2],b[ptr]); add(3,pos,1ll*b[ptr]*ptr%mod);up(sum[3],1ll*b[ptr]*ptr%mod); } /**j<i,b[j]<a[i]**/ pos = lower_bound(p+1,p+1+cnt,a[i])-p; --pos; LL tmp =ask(0,pos); if(tmp!=0) { tmp = 1ll*i*a[i]%mod*tmp%mod;up(ret,tmp); //up(ret,ksc(1ll*i*a[i]%mod,tmp)); tmp = -(ask(1,pos)*a[i]%mod); //tmp = -ksc(ask(1,pos),a[i]); up(tmp,mod); up(ret,tmp); tmp = -(ask(2,pos)*i%mod); //tmp = -ksc(ask(2,pos),i); up(tmp,mod); up(ret,tmp); up(ret,ask(3,pos)); } /*********/ /**j<i,b[j]>a[i]**/ pos = upper_bound(p+1,p+1+cnt,a[i])-p; if(pos==cnt+1)continue; --pos; tmp = sum[0]-ask(0,pos); if(tmp==0)continue; tmp = -(1ll*i*a[i]%mod*tmp%mod); //tmp= -ksc(1ll*i*a[i]%mod,tmp); up(tmp,mod); up(ret,tmp); tmp = (sum[1]-ask(1,pos)+mod)%mod; tmp = tmp*a[i]%mod; //tmp = ksc(tmp,a[i]); up(ret,tmp); tmp = (sum[2]-ask(2,pos)+mod)%mod; tmp = tmp*i%mod; //tmp = ksc(tmp,i); up(ret,tmp); tmp = (sum[3]-ask(3,pos)+mod)%mod; tmp = (mod-tmp)%mod; up(ret,tmp); /*********/ } init(); ptr=m; for(int i=n; i; --i) { int pos; for(; ptr>i&&ptr; --ptr) { pos = lower_bound(p+1,p+1+cnt,b[ptr])-p; add(0,pos,1);++sum[0]; add(1,pos,ptr);up(sum[1],ptr); add(2,pos,b[ptr]);up(sum[2],b[ptr]); add(3,pos,1ll*b[ptr]*ptr%mod);up(sum[3],1ll*b[ptr]*ptr%mod); } /**j>i,b[j]>a[i]**/ pos = upper_bound(p+1,p+1+cnt,a[i])-p; --pos; if(pos!=cnt) { LL tmp = sum[0]-ask(0,pos); if(tmp!=0) { tmp = 1ll*i*a[i]%mod*tmp%mod;up(ret,tmp); //up(ret,ksc(1ll*i*a[i]%mod,tmp)); tmp = (sum[1]-ask(1,pos)+mod)%mod; tmp = -(tmp*a[i]%mod); //tmp = -ksc(tmp,a[i]); up(tmp,mod); up(ret,tmp); tmp = (sum[2]-ask(2,pos)+mod)%mod; tmp = -(tmp*i%mod); //tmp = -ksc(tmp,i); up(tmp,mod); up(ret,tmp); tmp = (sum[3]-ask(3,pos)+mod)%mod; up(ret,tmp); } } /*********/ /**j>i,b[j]<a[i]**/ pos = lower_bound(p+1,p+1+cnt,a[i])-p; --pos; LL tmp = ask(0,pos); if(tmp==0)continue; tmp =-(1ll*i*a[i]%mod*tmp%mod); //tmp= -ksc(1ll*i*a[i]%mod,tmp); up(tmp,mod); up(ret,tmp); tmp = ask(1,pos); tmp = tmp*a[i]%mod; //tmp = ksc(tmp,a[i]); up(ret,tmp); tmp = ask(2,pos); tmp = tmp*i%mod; //tmp = ksc(tmp,i); up(ret,tmp); tmp = ask(3,pos); tmp = (mod-tmp)%mod; up(ret,tmp); /*********/ } printf("Case #%d: %lld\n",++kase,ret); } return 0;}
玲珑学院OJ 1023 - Magic boy Bi Luo with his excited math problem 树状数组暴力
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。