树状数组

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个查询，每组一个区间，询问区间中所有数的乘积的欧拉函数9+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你个炒鸡大菜鸡。

# 题目链接 题意： 这题是问一个长度为n的循环数组中，逆序对最少的个数。。。

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

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

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

# 三维树状数组 容斥那里注意一下。 多组数据因为忘记清空c数组而wa了1次，细心！

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}

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

Inversions **Time Limit:**250MS **Memory Limit:**4096KB 64bit IO Format:%I64d & %I64u Submit Status Description 180. Inversions # time limit per test: 0.25 sec. memory limit per test: 4096 KB

这道题可以总结的地方不少。 １：对于一组乱序数列，每次只能交换相邻元素，达到有序交换的次数就是原数列中你逆序对的个数。

poj 2481 题目链接 题意：给定n个区间，问对于每个区间，有多少个区间真包含该区间（真包含的意思是说，两个区间不能完全重合）

poj 2352题目链接 题意：给出n个星星的位置，一个星星的level定义为其左下角（不严格）星星的数量。