2014 Multi-University Training Contest 5

hdu4911

max(逆序数-k，0）

  1 #include <iostream>
  2 #include<stdio.h>
  3 #include<vector>
  4 #include<queue>
  5 #include<stack>
  6 #include<string.h>
  7 #include<algorithm>
  8 #include<map>
  9 using namespace std;
 10 #define LL long long
 11 #define gcd(a,b) (b==0?a:gcd(b,a%b))
 12 #define lcm(a,b) (a*b/gcd(a,b))
 13 //O（n）求素数，1-n的欧拉数
 14 #define N 100010
 15 //A^x = A^(x % Phi(C) + Phi(C)) (mod C)
 16 map<int,int>f;
 17 struct node
 18 {
 19     int a;
 20     int id;
 21 }p[N];
 22 int s[N<<2],b[N];
 23 void up(int w)
 24 {
 25     s[w]  = s[w<<1]+s[w<<1|1];
 26 }
 27 void build(int l,int r,int w)
 28 {
 29     if(l==r)
 30     {
 31         s[w] = 0;
 32         return ;
 33     }
 34     int m = (l+r)>>1;
 35     build(l,m,w<<1);
 36     build(m+1,r,w<<1|1);
 37     up(w);
 38 }
 39 void update(int p,int d,int l,int r,int w)
 40 {
 41     if(l==r)
 42     {
 43         s[w] += d;
 44         return ;
 45     }
 46     int m  =(l+r)>>1;
 47     if(p<=m)
 48     update(p,d,l,m,w<<1);
 49     else
 50     update(p,d,m+1,r,w<<1|1);
 51     up(w);
 52 
 53 }
 54 int query(int a,int b,int l,int r,int w)
 55 {
 56     if(a<=l&&b>=r)
 57         return s[w];
 58     int m = (l+r)>>1;
 59     int res = 0;
 60     if(a<=m) res+=query(a,b,l,m,w<<1);
 61     if(b>m) res+=query(a,b,m+1,r,w<<1|1);
 62     return res;
 63 }
 64 bool cmp(node a,node b)
 65 {
 66     return a.a<b.a;
 67 }
 68 int main()
 69 {
 70     int n,i,j,k;
 71     while(scanf("%d%d",&n,&k)!=EOF)
 72     {
 73         f.clear();
 74         for(i = 1; i<= n; i++)
 75         {
 76             scanf("%d",&p[i].a);
 77             p[i].id = i;
 78             b[i] = p[i].a;
 79         }
 80         sort(b+1,b+n+1);
 81         f[b[1]] = 1;
 82         int o = 1;
 83         for(i = 2; i<= n; i++)
 84             if(b[i]!=b[i-1])
 85             {
 86                 f[b[i]] = ++o;
 87             }
 88         build(1,o,1);
 89         LL s = 0 ;
 90         for(i = 1; i<= n ;i++)
 91         {
 92             //cout<<f[p[i].a]<<endl;
 93             int kk = 0;
 94             if(f[p[i].a]<o)
 95             kk = query(f[p[i].a]+1,o,1,o,1);
 96             update(f[p[i].a],1,1,o,1);
 97             s+=kk;
 98         }
 99         LL x = 0;
100         s = max(x,s-k);
101         cout<<s<<endl;
102     }
103     return 0;
104 }

View Code

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，依次扫描一遍就可得出结果。

  1 #include <iostream>
  2 #include<stdio.h>
  3 #include<vector>
  4 #include<queue>
  5 #include<stack>
  6 #include<string.h>
  7 #include<algorithm>
  8 #include<map>
  9 using namespace std;
 10 #define LL __int64
 11 #define gcd(a,b) (b==0?a:gcd(b,a%b))
 12 #define lcm(a,b) (a*b/gcd(a,b))
 13 #define N 100005
 14 #define mod 1000000007
 15 struct node
 16 {
 17     int a,b;
 18     int id;
 19 } p[N];
 20 LL lz[N<<2],s[N<<2];
 21 LL sum[N<<2];
 22 int po[N];
 23 LL mul(LL a,LL b,LL m)
 24 {
 25     LL d,t;
 26     d=1;
 27     t=a;
 28     while (b>0)
 29     {
 30         if (b%2==1)
 31         d=(d*t)%m;
 32         b/=2;
 33         t=(t*t)%m;
 34     }
 35     return d;
 36 }
 37 bool cmp(node x,node y)
 38 {
 39     return x.a<y.a;
 40 }
 41 bool cmpp(node x,node y)
 42 {
 43     return x.b<y.b;
 44 }
 45 void up(int w)
 46 {
 47     s[w] = (s[w<<1]+s[w<<1|1])%mod;
 48 }
 49 void build(int l,int r,int w)
 50 {
 51     lz[w] = 1;
 52     if(l==r)
 53     {
 54         s[w] = 0;
 55         return ;
 56     }
 57     int m = (l+r)>>1;
 58     build(l,m,w<<1);
 59     build(m+1,r,w<<1|1);
 60     up(w);
 61 }
 62 void down(int w,int m)
 63 {
 64     if(lz[w]!=1)
 65     {
 66         lz[w<<1] = (lz[w<<1]*lz[w])%mod;
 67         lz[w<<1|1] = (lz[w<<1|1]*lz[w])%mod;
 68         s[w<<1] = (s[w<<1]*lz[w])%mod;
 69         s[w<<1|1] = (s[w<<1|1]*lz[w])%mod;
 70         lz[w] = 1;
 71     }
 72 }
 73 void update(int p,LL d,int l,int r,int w)
 74 {
 75     if(l==r)
 76     {
 77         s[w] = d;
 78         return ;
 79     }
 80     down(w,r-l+1);
 81     int m = (l+r)>>1;
 82     if(p<=m)
 83         update(p,d,l,m,w<<1);
 84     else
 85         update(p,d,m+1,r,w<<1|1);
 86     up(w);
 87 }
 88 void update1(int a,int b,LL d,int l,int r,int w)
 89 {
 90     if(a<=l&&b>=r)
 91     {
 92         s[w] = (s[w]*d)%mod;
 93         lz[w] = (lz[w]*d)%mod;
 94         return ;
 95     }
 96     down(w,r-l+1);
 97     int m = (l+r)>>1;
 98     if(a<=m) update1(a,b,d,l,m,w<<1);
 99     if(b>m) update1(a,b,d,m+1,r,w<<1|1);
100     up(w);
101 }
102 LL query(int a,int b,int l,int r,int w)
103 {
104     if(a<=l&&b>=r) return s[w];
105     int m = (l+r)>>1;
106     LL res = 0;
107     if(a<=m) res+=query(a,b,l,m,w<<1);
108     if(b>m) res = (res+query(a,b,m+1,r,w<<1|1))%mod;
109     return res;
110 }
111 void up1(int w)
112 {
113     sum[w] = sum[w<<1]+sum[w<<1|1];
114 }
115 void build1(int l,int r,int w)
116 {
117     if(l==r)
118     {
119         sum[l] = 0;
120         return ;
121     }
122     int m = (l+r)>>1;
123     build1(l,m,w<<1);
124     build1(m+1,r,w<<1|1);
125     up1(w);
126 }
127 void update2(int p,int l,int r,int w)
128 {
129     if(l==r)
130     {
131         sum[w] = 1;
132         return ;
133     }
134     int m = (l+r)>>1;
135     if(p<=m)
136     update2(p,l,m,w<<1);
137     else update2(p,m+1,r,w<<1|1);
138     up1(w);
139 }
140 int query1(int a,int b,int l,int r,int w)
141 {
142     if(a<=l&&b>=r)
143     {
144         return sum[w];
145     }
146     int m = (l+r)>>1;
147     int res=0;
148     if(a<=m) res+=query1(a,b,l,m,w<<1);
149     if(b>m) res+=query1(a,b,m+1,r,w<<1|1);
150     return res;
151 }
152 int main()
153 {
154     int n,i;
155     while(scanf("%d",&n)!=EOF)
156     {
157         memset(sum,0,sizeof(sum));
158         for(i = 1; i<= n; i++)
159         {
160             scanf("%d%d",&p[i].a,&p[i].b);
161             p[i].id = i;
162         }
163         sort(p+1,p+n+1,cmp);
164         for(i = 1; i <= n ; i++)
165         {
166             po[p[i].id] = i;
167         }
168         sort(p+1,p+n+1,cmpp);
169         build(1,n,1);
170         LL ans = 0;
171         build1(1,n,1);
172         for(i = 1; i <= n; i++)
173         {
174             int k = query1(1,po[p[i].id],1,n,1);
175             //cout<<k<<" "<<p[i].a<<" "<<po[p[i].id]<<endl;
176             update2(po[p[i].id],1,n,1);
177             update(po[p[i].id],mul(2,p[i].a+k,mod),1,n,1);
178             LL ss = query(po[p[i].id],n,1,n,1);
179            // cout<<ss<<endl;
180             ans=(ans+(mul(3,p[i].b,mod)*ss)%mod)%mod;
181             if(po[p[i].id]<n)
182             update1(po[p[i].id]+1,n,2,1,n,1);
183         }
184         printf("%I64d
",ans);
185     }
186     return 0;
187 }

View Code

  1 #include <iostream>
  2 #include<stdio.h>
  3 #include<vector>
  4 #include<queue>
  5 #include<stack>
  6 #include<string.h>
  7 #include<algorithm>
  8 #include<map>
  9 using namespace std;
 10 #define LL __int64
 11 #define gcd(a,b) (b==0?a:gcd(b,a%b))
 12 #define lcm(a,b) (a*b/gcd(a,b))
 13 #define N 100005
 14 #define mod 1000000007
 15 struct node
 16 {
 17     int a,b;
 18     int id;
 19 } p[N];
 20 LL lz[N<<2],s[N<<2];
 21 LL sum[N<<2];
 22 int po[N];
 23 LL mul(LL a,LL b,LL m)
 24 {
 25     LL d,t;
 26     d=1;
 27     t=a;
 28     while (b>0)
 29     {
 30         if (b%2==1)
 31         d=(d*t)%m;
 32         b/=2;
 33         t=(t*t)%m;
 34     }
 35     return d;
 36 }
 37 bool cmp(node x,node y)
 38 {
 39     return x.a<y.a;
 40 }
 41 bool cmpp(node x,node y)
 42 {
 43     return x.b<y.b;
 44 }
 45 void up(int w)
 46 {
 47     s[w] = (s[w<<1]+s[w<<1|1])%mod;
 48 }
 49 void build(int l,int r,int w)
 50 {
 51     lz[w] = 1;
 52     if(l==r)
 53     {
 54         s[w] = 0;
 55         return ;
 56     }
 57     int m = (l+r)>>1;
 58     build(l,m,w<<1);
 59     build(m+1,r,w<<1|1);
 60     up(w);
 61 }
 62 void down(int w,int m)
 63 {
 64     if(lz[w]!=1)
 65     {
 66         lz[w<<1] = (lz[w<<1]*lz[w])%mod;
 67         lz[w<<1|1] = (lz[w<<1|1]*lz[w])%mod;
 68         s[w<<1] = (s[w<<1]*lz[w])%mod;
 69         s[w<<1|1] = (s[w<<1|1]*lz[w])%mod;
 70         lz[w] = 1;
 71     }
 72 }
 73 void update(int p,LL d,int l,int r,int w)
 74 {
 75     if(l==r)
 76     {
 77         s[w] = d;
 78         return ;
 79     }
 80     down(w,r-l+1);
 81     int m = (l+r)>>1;
 82     if(p<=m)
 83         update(p,d,l,m,w<<1);
 84     else
 85         update(p,d,m+1,r,w<<1|1);
 86     up(w);
 87 }
 88 void update1(int a,int b,LL d,int l,int r,int w)
 89 {
 90     if(a<=l&&b>=r)
 91     {
 92         s[w] = (s[w]*d)%mod;
 93         lz[w] = (lz[w]*d)%mod;
 94         return ;
 95     }
 96     down(w,r-l+1);
 97     int m = (l+r)>>1;
 98     if(a<=m) update1(a,b,d,l,m,w<<1);
 99     if(b>m) update1(a,b,d,m+1,r,w<<1|1);
100     up(w);
101 }
102 LL query(int a,int b,int l,int r,int w)
103 {
104     if(a<=l&&b>=r) return s[w];
105     int m = (l+r)>>1;
106     LL res = 0;
107     if(a<=m) res+=query(a,b,l,m,w<<1);
108     if(b>m) res = (res+query(a,b,m+1,r,w<<1|1))%mod;
109     return res;
110 }
111 void up1(int w)
112 {
113     sum[w] = sum[w<<1]+sum[w<<1|1];
114 }
115 void build1(int l,int r,int w)
116 {
117     if(l==r)
118     {
119         sum[l] = 0;
120         return ;
121     }
122     int m = (l+r)>>1;
123     build1(l,m,w<<1);
124     build1(m+1,r,w<<1|1);
125     up1(w);
126 }
127 void update2(int p,int l,int r,int w)
128 {
129     if(l==r)
130     {
131         sum[w] = 1;
132         return ;
133     }
134     int m = (l+r)>>1;
135     if(p<=m)
136     update2(p,l,m,w<<1);
137     else update2(p,m+1,r,w<<1|1);
138     up1(w);
139 }
140 int query1(int a,int b,int l,int r,int w)
141 {
142     if(a<=l&&b>=r)
143     {
144         return sum[w];
145     }
146     int m = (l+r)>>1;
147     int res=0;
148     if(a<=m) res+=query1(a,b,l,m,w<<1);
149     if(b>m) res+=query1(a,b,m+1,r,w<<1|1);
150     return res;
151 }
152 int main()
153 {
154     int n,i;
155     while(scanf("%d",&n)!=EOF)
156     {
157         memset(sum,0,sizeof(sum));
158         for(i = 1; i<= n; i++)
159         {
160             scanf("%d%d",&p[i].a,&p[i].b);
161             p[i].id = i;
162         }
163         sort(p+1,p+n+1,cmp);
164         for(i = 1; i <= n ; i++)
165         {
166             po[p[i].id] = i;
167         }
168         sort(p+1,p+n+1,cmpp);
169         build(1,n,1);
170         LL ans = 0;
171         build1(1,n,1);
172         for(i = 1; i <= n; i++)
173         {
174             int k = query1(1,po[p[i].id],1,n,1);
175             //cout<<k<<" "<<p[i].a<<" "<<po[p[i].id]<<endl;
176             update2(po[p[i].id],1,n,1);
177             update(po[p[i].id],mul(2,p[i].a+k,mod),1,n,1);
178             LL ss = query(po[p[i].id],n,1,n,1);
179            // cout<<ss<<endl;
180             ans=(ans+(mul(3,p[i].b,mod)*ss)%mod)%mod;
181             if(po[p[i].id]<n)
182             update1(po[p[i].id]+1,n,2,1,n,1);
183         }
184         printf("%I64d
",ans);
185     }
186     return 0;
187 }

View Code