树状数组

https://vjudge.net/problem/47450/origin 题意： # 有一个含有n个数的序列，m个询问。问 [l, r] 区间内与所有数都互质的数有几个？ 思路： # 想到了预处理每个数最左最右的，最远的互质的数的范围。。

题目链接 题意： # If two point such as (xi,yi,zi) and (xj,yj,zj) xi≥xj yi≥yj zi≥zj, the bigger one level add 1 问每个point的level是多少。 思路： # cdq分治，先去重并统计相同的点的数量，需要注意要记录原id对应到了哪个新id

Description # 有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

题目链接 题意：有２种货币，分别为C和D.给出n种资源的代价和美丽度，每种资源只能用其中一种资源购买。现在拥有货币C的数量是c，拥有货币D的数量是d.然后恰好买２个资源，问最大美丽度，不能的话输出０．

题目链接 题意：给出 n 个数，q 个查询，每组一个区间，询问区间中所有数的乘积的欧拉函数对 1e9+7 取模的答案是多少。 思路：这道题需要一点欧拉函数的知识。 phi(n) 是欧拉函数，意义为小于等于 n 并且与 n 互质的数的个数。

题目链接 题意：有 n 个数，每次可以删除掉数值相同并且所在位置成等差数列（只删 2 个数或者只删 1 个数应该也是可以的），删掉这些数以后可以将剩下的数重新以任意顺序排列，称为一次操作。现在给出 m 个询问，每个询问一个区间 [l,r]，问删光区间 [l,r] 中的数最少需要的操作次数。

题目链接 题意： how many pairs of integers l and r are there, such that 1 ≤ l < r ≤ n and sequence b = _a_1_a_2… a__l__a__r__a__r + 1… a__n has no more than k inversions. 我花了两个小时才看懂题。。。。一直没懂b数列中a[l]和a[r]怎么就挨着了。。。 其实意思是。。。只保留a数列中1..l和r..n的。。。构成b数列。。。然后b数列的逆序对数小于等于k.问这样的l,r的对数。

http://www.lydsy.com/JudgeOnline/problem.php?id=3289 题意：中文题目，简单来说就是求某一区间内的逆序对数。 思路：逆序对数想到树状数组。不过写莫队转移的时候没弄明白。。。。大概是树状数组理解的还不够透彻。。。需要复习一下了。。。

http://codeforces.com/problemset/problem/552/A 题意：一个100*100的网格。然后给n个矩形。每个格子中填上包含这个格子的矩形的个数。最后问所有格子的和。 思路：树状数组搞得…然而..直接求所有矩形面积的和就可以啊喂。。o(n)。。。111qqz你个炒鸡大菜鸡。

# 题目链接 题意： 这题是问一个长度为n的循环数组中，逆序对最少的个数。。。 我们可以先用树状数组求出初始的数列的逆序对。。。 然后其他的可以通过递推得到。。。。

Cinema in Akiba Cinema in Akiba (CIA) is a small but very popular cinema in Akihabara. Every night the cinema is full of people. The layout of CIA is very interesting, as there is only one row so that every audience can enjoy the wonderful movies without any annoyance by other audiences sitting in front of him/her. The ticket for CIA is strange, too. There are n seats in CIA and they are numbered from 1 to n in order. Apparently, n tickets will be sold everyday. When buying a ticket, if there are k tickets left, your ticket number will be an integer i (1 ≤ i ≤ k), and you should choose theith empty seat (not occupied by others) and sit down for the film.

比较水． 唯一一点需要注意的是… 可能有重复元素… 因为我的思路是用两棵一维树状数组搞.. 每个点标记为1 然后看矩形的两个方向中是否至少有一个方向上和等于长度…

比赛的时候没过．还以为是树状数组写残了． 但实际上是有自己不知道的东西． 这种博弈叫　nim游戏 所以这是一个二维的nim游戏． **nim游戏的性质是xor 和为0必败，否则必胜． xor和也有前缀和性质，所以可以用树状数组维护．

题目链接 喵呜，离散树状数组。 这道题由于相同的值加和的时候只算一次，所以比较伤脑筋== 怎么办呢？ 我们发现对于一个值，由于相同的只算一次，所以在任意时间内，这个值只需要出现一次。

树状数组，更新区间，查询单点，区别是加了一个a%k==0的条件限制…. 我们观察到k很小，于是按照k分类…. 每一类再按照余数分类，一共55棵树（1+2+3+…+10）

# 三维树状数组 容斥那里注意一下。 多组数据因为忘记清空c数组而wa了1次，细心！ 代码实现 1/************************************************************************* 2 > File Name: code/hdu/3584.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: 2015年08月07日 星期五 14时01分53秒 6 ************************************************************************/ 7 8#include<iostream> 9#include<iomanip> 10#include<cstdio> 11#include<algorithm> 12#include<cmath> 13#include<cstring> 14#include<string> 15#include<map> 16#include<set> 17#include<queue> 18#include<vector> 19#include<stack> 20#define y0 abc111qqz 21#define y1 hust111qqz 22#define yn hez111qqz 23#define j1 cute111qqz 24#define tm crazy111qqz 25#define lr dying111qqz 26using namespace std; 27#define REP(i, n) for (int i=0;i<int(n);++i) 28typedef long long LL; 29typedef unsigned long long ULL; 30const int inf = 0x7fffffff; 31const int N=1E2+5; 32int c[N][N][N]; 33int n,m; 34int x1,y1,z1,x2,y2,z2; 35int lowbit( int x) 36{ 37 return x&(-x); 38} 39void update ( int x,int y,int z,int delta) 40{ 41 for ( int i = x; i <= n ; i = i + lowbit(i)) 42 { 43 for ( int j = y ; j <= n ; j = j + lowbit(j)) 44 { 45 for ( int k = z ; k <= n ; k = k + lowbit(k)) 46 { 47 c[i][j][k] += delta; 48 } 49 } 50 } 51} 52 53int sum (int x,int y,int z) 54{ 55 int res = 0; 56 for ( int i = x; i >= 1 ; i -= lowbit(i)) 57 { 58 for ( int j = y ; j >= 1 ; j -= lowbit(j)) 59 { 60 for ( int k = z ; k >= 1 ; k -= lowbit(k)) 61 { 62 res = res + c[i][j][k]; 63 } 64 } 65 } 66 return res; 67} 68int main() 69{ 70 int op; 71 while (scanf("%d %d",&n,&m)!=EOF) 72 { 73 memset(c,0,sizeof(c)); 74 for ( int i = 1 ; i <= m ; i ++ ) 75 { 76 scanf("%d",&op); 77 if (op) 78 { 79 scanf("%d %d %d %d %d %d",&x1,&y1,&z1,&x2,&y2,&z2); 80 update (x1,y1,z1,1); 81 update (x1,y1,z2+1,1); 82 update (x1,y2+1,z1,1); 83 update (x2+1,y1,z1,1); 84 85 update (x2+1,y2+1,z1,1); 86 update (x2+1,y1,z2+1,1); 87 update (x1,y2+1,z2+1,1); 88 update (x2+1,y2+1,z2+1,1); 89 90 } 91 else 92 { 93 scanf("%d %d %d",&x1,&y1,&z1); 94 cout<<sum(x1,y1,z1)%2<<endl; 95 } 96 } 97 } 98 99 return 0; 100}

1 和上一道类似，也是更新区间，查询单点。 用到了容斥原理。 代码实现 1/************************************************************************* 2 > File Name: code/poj/2155.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: 2015年08月07日 星期五 00时42分38秒 6 ************************************************************************/ 7 8#include<iostream> 9#include<iomanip> 10#include<cstdio> 11#include<algorithm> 12#include<cmath> 13#include<cstring> 14#include<string> 15#include<map> 16#include<set> 17#include<queue> 18#include<vector> 19#include<stack> 20#define y0 abc111qqz 21#define y1 hust111qqz 22#define yn hez111qqz 23#define j1 cute111qqz 24#define tm crazy111qqz 25#define lr dying111qqz 26using namespace std; 27#define REP(i, n) for (int i=0;i<int(n);++i) 28typedef long long LL; 29typedef unsigned long long ULL; 30const int inf = 0x7fffffff; 31const int N=1E3+7; 32int c[N][N]; 33int n,m,x1,x2,y1,y2,x,y,t; 34 35int lowbit ( int x) 36{ 37 return x&(-x); 38} 39void update ( int x,int y ,int delta) 40{ 41 for ( int i = x ; i <= n ; i = i + lowbit(i)) 42 { 43 for ( int j = y; j <= n ; j = j + lowbit(j)) 44 { 45 c[i][j] = c[i][j] + delta; 46 } 47 } 48} 49int sum ( int x,int y) 50{ 51 int res = 0; 52 for ( int i = x; i >= 1 ; i = i - lowbit (i)) 53 { 54 for ( int j = y ; j >= 1 ; j = j - lowbit (j)) 55 { 56 57 res = res + c[i][j]; 58 } 59 } 60 return res; 61} 62int main() 63{ 64 int T; 65 cin>>T; 66 while (T--) 67 { 68 memset(c,0,sizeof(c)); 69 scanf("%d %d",&n,&t); 70 for ( int i = 1; i <= t; i ++ ) 71 { 72 char cmd; 73 cin>>cmd; 74 if (cmd=='C') 75 { 76 scanf("%d %d %d %d",&x1,&y1,&x2,&y2); 77// cout<<"*******"<<c[2][1]<<" "<<c[2][2]<<endl; 78 update (x1,y1,1); 79 update (x2+1,y1,1); 80 update (x1,y2+1,1); 81 update (x2+1,y2+1,1); 82// cout<<"*******"<<c[2][1]<<" "<<c[2][2]<<endl; 83 } 84 else 85 { 86 scanf("%d %d",&x,&y); 87 int tmp; 88// cout<<"sum(x)(y):"<<sum(x,y)<<endl; 89// cout<<"sum(x-1,y-1):"<<sum(x-1,y-1)<<endl; 90// cout<<"sum(x-1,y):"<<sum(x-1,y)<<endl; 91// cout<<"sum(x,y-1):"<<sum(x,y-1)<<endl; 92 tmp =sum(x,y)+sum(x-1,y-1)-sum(x-1,y)-sum(x,y-1); 93// cout<<"tmp:"<<tmp<<endl; 94 if (sum(x,y)%2==0) 95 cout<<0<<endl; 96 else cout<<1<<endl; 97 } 98// cout<<"*****************"<<endl; 99// for ( int ii = 1 ; ii <= n ; ii++) 100// { 101// for ( int jj = 1 ; jj <= n ; jj++ ) 102// { 103// cout<<c[ii][jj]<<" "; 104// } 105// cout<<endl; 106// } 107// cout<<"*************************"<<endl; 108// 109 } 110 cout<<endl; 111 } 112 113 return 0; 114}

这道题和之前做的树状数组略有不同。 以前的都是更新单点，查询区间，这次反了过来。 做法差不多。 如果更新区间【x,y】增加１ 那么只要 update (x,1),update (y+1,-1) 问单点的时候，sum(i)就是i点的值，而不是1..i的和。