经典入门题，敌兵布阵
http://acm.hdu.edu.cn/showproblem.php?pid=1166
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 using namespace std; 5 6 int n,aa[50005],cc[50005]; 7 8 int lowbit(int x){ 9 return x&(-x); 10 } 11 12 void add(int x,int y){ 13 while(x<=n){ 14 cc[x]+=y; 15 x+=lowbit(x); 16 } 17 } 18 19 int sum(int x){ 20 int s=0; 21 while(x>0){ 22 s+=cc[x]; 23 x-=lowbit(x); 24 } 25 return s; 26 } 27 28 int main(){ 29 int t,countn=1; 30 char str[20]; 31 scanf("%d",&t); 32 while(t--){ 33 memset(aa,0,sizeof(aa)); 34 memset(cc,0,sizeof(cc)); 35 scanf("%d",&n); 36 for(int i=1;i<=n;i++){ 37 scanf("%d",&aa[i]); 38 add(i,aa[i]); 39 } 40 printf("Case %d: ",countn); 41 while(~scanf("%s",str)){ 42 if(str[0]=='E') 43 break; 44 if(str[0]=='A'){ 45 int a,b; 46 scanf("%d%d",&a,&b); 47 add(a,b); 48 } 49 if(str[0]=='Q'){ 50 int a,b; 51 scanf("%d%d",&a,&b); 52 printf("%d ",sum(b)-sum(a-1)); 53 } 54 if(str[0]=='S'){ 55 int a,b; 56 scanf("%d%d",&a,&b); 57 add(a,-b); 58 } 59 } 60 countn++; 61 } 62 return 0; 63 }
-----------------------------------------------------------------------------------------
http://acm.hdu.edu.cn/showproblem.php?pid=4417
给定n个高度，有m个询问LR之间小于等于H的个数
1 #include <iostream> 2 #include <algorithm> 3 #include <string.h> 4 using namespace std; 5 #define bt(x) x&(-x) 6 const int maxn = 1e5+10; 7 int n, m, a[maxn], sum[maxn]; 8 struct Node{ 9 int x, y; 10 bool friend operator < (Node a, Node b){ 11 return a.x < b.x; 12 } 13 }T[maxn]; 14 struct Node2{ 15 int l, r, x, y; 16 bool friend operator < (Node2 a, Node2 b){ 17 return a.x < b.x; 18 } 19 }TT[maxn]; 20 void ad(int x, int xx){ 21 while(x <= n){ 22 a[x] += xx; 23 x += bt(x); 24 } 25 } 26 int q(int x){ 27 int sum = 0; 28 while(x){ 29 sum += a[x]; 30 x -= bt(x); 31 } 32 return sum; 33 } 34 int main(){ 35 int t; 36 scanf("%d", &t); 37 for(int tt = 1; tt <= t; ++tt){ 38 scanf("%d%d", &n, &m); 39 a[0] = 0; 40 for(int i = 1; i <= n; ++i){ 41 a[i] = 0; 42 scanf("%d", &T[i].x); 43 T[i].y = i; 44 } 45 sort(T+1, T+n+1); 46 for(int i = 1; i <= m; ++i){ 47 scanf("%d%d%d", &TT[i].l, &TT[i].r, &TT[i].x); 48 TT[i].y = i; 49 } 50 sort(TT+1, TT+m+1); 51 int num = 1; 52 printf("Case %d: ", tt); 53 for(int i = 1; i <= m; ++i){ 54 int xx = TT[i].x; 55 while(num <= n && xx >= T[num].x){ 56 int xxx = T[num].y; 57 ad(xxx, 1); 58 num ++; 59 } 60 sum[TT[i].y] = q(TT[i].r+1) - q(TT[i].l); 61 } 62 for(int i = 1; i <= m; ++i){ 63 printf("%d ", sum[i]); 64 } 65 } 66 return 0; 67 }
-----------------------------------------------------------------------------------------
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=26&page=show_problem&problem=2330
一条街上住着n个乒乓球爱好者，有不同的能力值，每场比赛需要3个人（两名选手一名裁判）要求裁判住在选手中间并且能力值在两名选手中间，问一共可以组织多少种比赛
1 #include <iostream> 2 #include <string.h> 3 using namespace std; 4 #define ll long long 5 #define bt(x) x&(-x) 6 const int maxn = 1e5+10;; 7 int t, n, a[maxn], b[maxn], c[maxn], d[maxn]; 8 void add(int x, int y){ 9 while(x < maxn){ 10 d[x] += y; 11 x += bt(x); 12 } 13 } 14 int q(int x){ 15 int sum = 0; 16 while(x){ 17 sum += d[x]; 18 x -= bt(x); 19 } 20 return sum; 21 } 22 int main(){ 23 scanf("%d", &t); 24 while(t--){ 25 scanf("%d", &n); 26 memset(d, 0, sizeof(int)*maxn); 27 for(int i = 1; i <= n; ++i){ 28 scanf("%d", &a[i]); 29 add(a[i], 1); 30 b[i] = q(a[i]-1); 31 } 32 memset(d, 0, sizeof(int)*maxn); 33 for(int i = n; i >= 1; --i){ 34 add(a[i], 1); 35 c[i] = q(a[i]-1); 36 } 37 ll sum = 0; 38 for(int i = 1; i <= n; ++i){ 39 sum = sum + (ll)b[i]*(n-i-c[i]) + (ll)c[i]*(i-b[i]-1); 40 } 41 printf("%lld ", sum); 42 } 43 return 0; 44 }
-----------------------------------------------------------------------------------------
http://poj.org/problem?id=2828
神奇的BIT
find函数，利用二进制来快速求出第k大数，只需log复杂度
1 #include <iostream> 2 #include <string.h> 3 using namespace std; 4 #define bt(x) x&(-x) 5 const int maxn = 200009; 6 int n, a[maxn], b[maxn], sum[maxn], c[maxn]; 7 void add(int x, int y){ 8 while(x <= n){ 9 sum[x] += y; 10 x += bt(x); 11 } 12 } 13 int f(int x){ 14 int xx = 0, yy = 0; 15 for(int i = 20; i >= 0; --i){ 16 xx += 1<<i; 17 if(xx > n || yy + sum[xx] >= x){ 18 xx -= 1<<i; 19 }else{ 20 yy += sum[xx]; 21 } 22 } 23 return xx+1; 24 } 25 int main(){ 26 while(~scanf("%d", &n)){ 27 memset(sum, 0, sizeof(int)*maxn); 28 for(int i = 1; i <= n; ++i){ 29 scanf("%d%d", &a[i], &b[i]); 30 add(i, 1); 31 } 32 for(int i = n; i >= 1; --i){ 33 int xx = f(a[i]+1); 34 c[xx] = b[i]; 35 add(xx, -1); 36 } 37 for(int i = 1; i <= n; ++i){ 38 printf("%d%c", c[i], i == n ? ' ' : ' '); 39 } 40 } 41 return 0; 42 }
-----------------------------------------------------------------------------------------
区间更新
推荐博客http://www.cnblogs.com/lcf-2000/p/5866170.html
自从有了它之后。。什么？线段树是什么？
1 #include <iostream> 2 using namespace std; 3 #define ll long long 4 #define bt(x) x&-x 5 const int maxn = 100009; 6 int n, m, x, y; 7 ll xx, c1[maxn], c2[maxn]; 8 void add(int x, ll y){ 9 for(int i = x; i <= n; i += bt(i)) c1[i] += y, c2[i] += x*y; 10 } 11 ll f(int x){ 12 ll sum = 0; 13 for(int i = x; i; i -= bt(i)) sum += c1[i]*(x+1) - c2[i]; 14 return sum; 15 } 16 int main(){ 17 scanf("%d%d", &n, &m); 18 for(int i = 1; i <= n; ++i){ 19 scanf("%lld", &xx); 20 add(i, xx), add(i+1, -xx); 21 } 22 char str[3]; 23 for(int i = 0; i < m; ++i){ 24 scanf("%s", str); 25 if(str[0] == 'Q'){ 26 scanf("%d%d", &x, &y); 27 printf("%lld ", f(y)-f(x-1)); 28 }else{ 29 scanf("%d%d%lld", &x, &y, &xx); 30 add(x, xx), add(y+1, -xx); 31 } 32 } 33 return 0; 34 }
-----------------------------------------------------------------------------------------
https://loj.ac/problem/524
如果没有X直接判断逆序对奇偶性，否则判断X个数的奇偶性（1要特判）
因为最后一个放的人肯定可以放成胜态
1 #include <iostream> 2 #include <map> 3 #include <string.h> 4 #include <algorithm> 5 using namespace std; 6 7 const int M = 1e9+5; 8 const int maxn = 100009; 9 char str[222]; 10 int a[maxn], n, numx, numi = 1, b[maxn], m[maxn]; 11 12 void add(int x){ 13 while(x <= numi){ 14 m[x] += 1; 15 x += (x&-x); 16 } 17 } 18 19 int f(int x){ 20 int sum = 0; 21 while(x){ 22 sum += m[x]; 23 x -= (x&-x); 24 } 25 return sum; 26 } 27 28 int q(){ 29 int num = 0; 30 for(int i = 1; i < numi; ++i){ 31 num += f(b[i]); 32 add(b[i]); 33 } 34 return num; 35 } 36 37 int main(){ 38 scanf("%d", &n); 39 for(int i = 0; i < n; ++i){ 40 scanf("%s", str); 41 if(str[0] == 'X') numx ++; 42 else a[numi++] = atoi(str); 43 } 44 if(!numx){ 45 for(int i = 1; i < numi; ++i) b[i] = i; 46 sort(b+1, b+numi, [](int x, int y){ 47 return a[x] < a[y]; 48 }); 49 if(q()&1) printf("W "); 50 else printf("L "); 51 return 0; 52 } 53 if(n == 1){ 54 return printf("L "), 0; 55 } 56 if(numx&1) printf("W "); 57 else printf("L "); 58 return 0; 59 }
-----------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------
只有不断学习才能进步！