这个周四开始学习树状数组，本以为假期已经学会了，结果做题才发现切掉的只是水题，果然是还不熟练啊。正好借此机会学习下C++的用法
练习题目清单：
AHDU1556 BPOJ2155 CPOJ2299 DPOJ3067 EPOJ2352 FPOJ2481 GPOJ3321 HPOJ1990 A：
题目：HDU1556
思路：树状数组，区间更新单点求值的题目
代码：
//MEMORY 600KB TIME 687MS
#include<cstdio>
#include<cstring>
using namespace std;
int n,i,a,b;
int c[100010];
int lowbit(int i)
{
return i&(-i);
}
void update(int i,int x)
{
while(i>0)
{
c[i]+=x;
i-=lowbit(i);
}
}
int sum(int i)
{
int res=0;
while(i<=n)
{
res+=c[i];
i+=lowbit(i);
}
return res;//第一次忘记写return了不过居然能有输出值
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(c,0,sizeof(c));
if(n!=0)
{
for(i=1; i<=n; i++)
{
scanf("%d%d",&a,&b);
update(b,1);
update(a-1,-1);
}
printf("%d",sum(1));//使最后一个数字输出的时候没有空格的方法
for(i=2; i<=n; i++)
printf(" %d",sum(i));
printf("\n");
}
}
}
B
题目：POJ2155
思路：一道二维数组的单点更新区间求和的问题,可以考虑格子只要修改一次就+1，对答案用2取余即可,因此只要修改(X1，Y1)(X2+1，Y2+1)(X1,Y2+1)(X2+1,Y1)四个点,对其加1即可。
代码：
//MEMORY 4308KB TIME 547MS
//就算只读入了一个字符也要用字符数组啊因为它还会有一个看不见的字符小尾巴君啊
#include<cstdio>
#include<cstring>
using namespace std;
int t,i,j,n,m,x,y,x1,x2,y1,y2,q;
char chr[5];
int c[1005][1005];
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int y)
{
for(i=x;i<1005;i+=lowbit(i))
for(j=y;j<1005;j+=lowbit(j))
c[i][j]++;
}
int sum(int x,int y){
int res=0;//OTZ需要赋初值0
for(i=x;i>0;i-=lowbit(i))
for(j=y;j>0;j-=lowbit(j))
res+=c[i][j];
return res;
}
int main()
{
scanf("%d",&t);
while(t--)
{
memset(c,0,sizeof(c));
scanf("%d%d",&n,&m);
// printf("%d%d\n",n,m);
while(m--){
// printf("%d\n",q);
scanf("%s",&chr);
if(chr[0]=='C'){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
update(x1,y1);
update(x1,y2+1);
update(x2+1,y1);
update(x2+1,y2+1);
}
else if(chr[0]=='Q'){
scanf("%d%d",&x,&y);
printf("%d\n",sum(x,y)%2);
}
}
printf("\n");
}
}
C
题目：POJ2299
思路：离散化是用的排序+二分查找的方法，应该还有更好的办法？哈希表什么的还没有学到呢【摊手…
代码：
//memory 6242kb time 766ms
//res输出的结果是long long
//用树状数组求逆序数外加离散化
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 500500
int c[MAX];
int a[MAX],h[MAX];
int i,n,b;
long long ans;
int lowbit(int x)
{
return x&(-x);
}
void update(int i,int m)
{
while(i<MAX)
{
c[i]+=m;
i+=lowbit(i);
}
}
int sum(int i){
int res=0;
while(i){
res+=c[i];
i-=lowbit(i);
}
return res;
}
int sea(int x){
int l=1,r=n;
int m;
while(l<=r){
m=(l+r)/2;
if(x==h[m])return m;
else if(x>h[m])l=m+1;
//OTZ如果这里不加上1的话会进入死循环【因为是整除所以如果是2+3的话l就会一直等于2到不了3
else r=m;//不过这里打m或者是m-1都可以退出不过输入m的话时间会...短？【797 to 766
}
}
int main()
{
while(scanf("%d",&n)!=EOF){
if(n!=0){
ans=0;
memset(c,0,sizeof(c));
memset(a,0,sizeof(a));
memset(h,0,sizeof(h));
for(i=1;i<=n;i++){
scanf("%d",&b);
a[i]=h[i]=b;
}
sort(h+1,h+n+1);
for(i=1;i<=n;i++){
ans+=(i-sum(sea(a[i]))-1);
update(sea(a[i]),1);
//printf("%d\n",ans);
}
printf("%I64d\n",ans);
}
}
}
D
题目：POJ3067
思路：先按照x从小到大排序，交点数就可以转换成为y的逆序对的个数了，当x一样的时候对y按照从小到大排序，这样同一个x就不会产生逆序对了
代码：
//memory 2972k time 391ms
//因为输出值可能会很大，所以在求和的时候改成用long long（要改好多处地方小心别遗漏下哪里的）
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<algorithm>
const int MAX=1010;
using namespace std;
struct node{
int x,y;
bool operator <(const node &a)const{
if(x==a.x)
return y<a.y;
return x<a.x;
}
}edge[MAX*MAX];//第一次的时候这里数组开小了【跪
int t,m,n,k,j,i;
long long ans;
int c[MAX];
int lowbit(int x){
return x&(-x);}
void update(int i){
while(i<MAX){
c[i]++;
i+=lowbit(i);
}
}
long long sum(int i){
long long res=0;
while(i){
res+=c[i];
i-=lowbit(i);
}
return res;
}
int main(){
scanf("%d",&t);
for(j=1;j<=t;j++){
memset(c,0,sizeof(c));
ans=0;
scanf("%d%d%d",&m,&n,&k);
for(i=1;i<=k;i++)
scanf("%d%d",&edge[i].x,&edge[i].y);
sort(edge+1,edge+k+1);
for(i=1;i<=k;i++){
update(edge[i].y);
ans+=(i-sum(edge[i].y));
}
printf("Test case %d: %I64d\n",j,ans);
}
return 0;
}
E
题目：POJ2352
思路：既然是按照顺序排列的那么像Y坐标这种没有用处的东西留着它干嘛直接一位树状数组切掉就行了。还是要小心x需要大于零的条件
代码：
//Memory 536kb time 375ms
#include<cstdio>
#include<cstring>
using namespace std;
#define MAX 32010
int c[MAX];
int star[15005];
int i,t,n,m,k,x,y;
int lowbit(int x)
{
return x&(-x);
}
void update(int i,int m)
{
while(i<MAX)
{
c[i]+=m;
i+=lowbit(i);
}
}
int sum(int i)
{
int res=0;
while(i)
{
res+=c[i];
i-=lowbit(i);
}
return res;
}
int main()
{
memset(c,0,sizeof(c));
memset(star,0,sizeof(star));
scanf("%d",&t);
for(i=0;i<t;i++)
{
scanf("%d%d",&x,&y);
star[sum(x+1)]++;//因为X可以等于0
update(x+1,1);
}
for(i=0;i<t;i++)
printf("%d\n",star[i]);
return 0;
}
F
题目：POJ2481
思路：
按照l从小到大排列，相同l按照r从大到小排列 一开始的思路是每插入一个就考虑0-l和r-MAX的最小值但是错了（EG:1-3,1-2,2-3） 于是改成求r-1的逆序数 考虑到0这个大大的坑，于是读入的l和r均加上二【反正平移一下又不会怎么样 考虑到有可能两个l和r完全相同，用a和b记录前一个l和r，t记录前一个的在他外面的长度数
代码：
//遇到了一个最沙比的问题...10^5=100000而不是10000
#include<cstdio>
#include<stdlib.h>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 100020
typedef struct _cow
{
int l,r,m;
};
struct _cow cow[MAXN];
int i,n,l,r,a,b,t;
int c[MAXN];
int d[MAXN];
int cmp(const void *a,const void *b)
{
struct _cow m1 = *(struct _cow*)a;
struct _cow m2 = *(struct _cow*)b;
if(m1.l!=m2.l)return m1.l<m2.l?-1:1;
else return m1.r>m2.r?-1:1;
}
int lowbit(int i)
{
return i&(-i);
}
void update(int x)
{
while(x<MAXN)
{
c[x]++;
x+=lowbit(x);
}
}
int sum(int x)
{
int res=0;
while(x)
{
res+=c[x];
x-=lowbit(x);
}
return res;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
if(n==0)return 0;
else
{
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
for(i=1; i<=n; i++)
{
scanf("%d%d",&l,&r);
cow[i].l=l+2;
cow[i].r=r+2;
cow[i].m=i;
}
qsort(cow+1,n,sizeof(cow[1]),cmp);
//for(i=1;i<=n;i++)printf("%d %d %d\n",cow[i].l,cow[i].r,cow[i].m);
a=cow[1].l;
b=cow[1].r;
t=0;
update(cow[1].l);
update(cow[1].r);
if(n>=2)
{
for(i=2; i<=n; i++)
{
update(cow[i].l);
update(cow[i].r);
if(cow[i].l==a&&cow[i].r==b)
d[cow[i].m]=t;
else
t=d[cow[i].m]=(i*2-sum(cow[i].r-1)-1);
//printf("%d %d\n",t,sum(cow[i].r-1));
a=cow[i].l;
b=cow[i].r;
}
for(i=1; i<n; i++)printf("%d ",d[i]);
printf("%d\n",d[n]);
}
else if(n==1)printf("0\n");
}
}
}
G
题目：POJ3321
思路：需要用DFS先对树处理一下，low和high数组是dfs自带的两个时间戳。
代码：
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int mx = 100005;
int n,m,u,v,i,j,step;
int low[mx];
int high[mx];
//bool vis[mx];没有用处了
bool d[mx];
int c[mx];
char chr[5];
//vector<int> tree[mx];//这么写就会tle
vector<vector<int> > tree(mx);
void dfs(int v){
int k;
low[v]=++step;
vis[v]=true;
for(k=0;k<tree[v].size();k++){
//if(!vis[tree[v][k]]){
//vis[tree[v][k]]=true;
dfs(tree[v][k]);
//}
}
high[v]=step;
}
int lowbit(int x){
return x&(-x);
}
void update(int x,int i){
while(x<=n){
c[x]+=i;
x+=lowbit(x);
}
}
int sum(int x){
int res = 0;
while(x){
res+=c[x];
x-=lowbit(x);
}
return res;
}
int main()
{
memset(vis,false,sizeof(vis));
scanf("%d",&n);
for(i=1;i<=n;i++)d[i]=true;
for(i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
tree[u].push_back(v);
//只让父节点保存子节点的坐标而不让子节点的坐标保存父节点的坐标
//就不需要判断有没有遍历过了
//tree[v].push_back(u);
}
step=0;
dfs(1);
for(i=1;i<=n;i++)
update(i,1);
scanf("%d",&m);
for(i=1;i<=m;i++){
scanf("%s%d",chr,&j);
if(chr[0]=='Q'){
int res = sum(high[j])-sum(low[j]-1);
printf("%d\n",res);
}
else if(chr[0]=='C')
{
if(d[j]){
//update(high[j],-1);
//update(low[j]-1,1);
update(low[j],-1);//【这里更新的是low[j]不是j，WA了一天简直蠢哭了
//..上面两行代码是注释掉上一行之后解锁的..来自队长=w=..
}
else
update(low[j],1);
d[j]=!d[j];
}
}
return 0;
}
H
题目：POJ1990
思路：【以前在网上找的题解，不过找不到出处了】
补出处：原来出自这里啊 1首先将n个点按照v从小到大排序（后面说的排在谁的前面，都是基于这个排序）。 这样，当i<j时有max{vi,vj}=vj， 2用两个树状数组，一个记录比xi小的点的个数a，一个记录比xi小的点的位置之和b， 然后，我们可以快速地求出xi与比xi小的点的所有距离的绝对值之和：ax[i]-b， 也可以方便地求出xi与比xi大的点的所有距离的绝对值之和：所有距离-b-(i-1-a)x[i]。 将二者相加，乘上vi，再把所有结果相加，搞定。
代码：
//MEMORY 692K TIME 16MS
//OTZ这道题不看题解简直不知道是用树状数组能过...差点两个for循环就循环去了...关键是尼玛啊假期还做过
//不过好在是借助题解外加死命推公式最后愣是给推出来了
//推了一个小时简直跪...不过比妹子好推【笑~
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int MAX=20010;
struct node{
int v,x;
bool operator <(const node &a)const{
if(v==a.v)
return x<a.x;
return v<a.v;
}
}cow[MAX];
//用C来记录点的个数d来记录点的和
int c[MAX];
int d[MAX];
int i,n,sum,a,b;
long long s,ans;
int lowbit(int x){
return x&(-x);
}
void update(int x,int m){
while(x<MAX){
c[x]++;
d[x]+=m;
x+=lowbit(x);
}
}
int sum1(int x){
int res=0;
while(x){
res+=c[x];
x-=lowbit(x);
}
return res;
}
int sum2(int x){
int res=0;
while(x){
res+=d[x];
x-=lowbit(x);
}
return res;
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d%d",&a,&b);
cow[i].v=a;
cow[i].x=b;
}
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
sort(cow+1,cow+1+n);
sum=0;
// for(i=1;i<=n;i++)printf("%d %d\n",cow[i].v,cow[i].x);
for(i=1;i<=n;i++)
{
sum+=cow[i].x;
update(cow[i].x,cow[i].x);
s=((sum1(cow[i].x)-1)*cow[i].x-(sum2(cow[i].x)-cow[i].x))+(sum-sum2(cow[i].x)-(i-sum1(cow[i].x))*cow[i].x);
ans+=s*cow[i].v;
//printf("%d %d %d %d %d\n",sum,sum1(cow[i].x)-1,sum2(cow[i].x)-cow[i].x,sum-sum2(cow[i].x),i-sum1(cow[i].x));
}
printf("%lld\n",ans);
}