树状数组

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

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

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

题目链接 题意：给出 n 个数，q 个查询，每组一个区间，询问区间中所有数的乘积的欧拉函数对 1e9+7 取模的答案是多少。

题目链接 题意：有 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.

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

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

# 题目链接

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.

比较水． 唯一一点需要注意的是… 可能有重复元素…

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

题目链接 喵呜，离散树状数组。 这道题由于相同的值加和的时候只算一次，所以比较伤脑筋==

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

# 三维树状数组

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}

这道题和之前做的树状数组略有不同。 以前的都是更新单点，查询区间，这次反了过来。