jquery网站模板下载,廊坊网站建站,音乐网站功能,劳动仲裁院网站建设基本知识#xff1a;
1.lowbit运算
int lowbit(int x){return x -x;
}
2.树状数组及其应用
a[N]是原始数组#xff1b;
c[N]是树状数组#xff0c;存放数组a中i号位之前的lowbit(i)个元素之和#xff0c;c[i]覆盖长度是lowbit(i)
特别强调 树状数组的下标必须从…基本知识
1.lowbit运算
int lowbit(int x){return x -x;
}
2.树状数组及其应用
a[N]是原始数组
c[N]是树状数组存放数组a中i号位之前的lowbit(i)个元素之和c[i]覆盖长度是lowbit(i)
特别强调 树状数组的下标必须从1开始
1.函数getSum(x)返回前x个数之和a[1]a[2]......a[x].
int getsum(int x){int res 0;//记录和for(int i x;i;i - lowbit(i))res tr[i];return res;
}
2.函数update(x,c).实现将第x个数加上一个数v的功能即a[x] c
void update(int x,int c){for(int i x;i n;i lowbit(i)){tr[i] c;}
} 例题1 在完成了分配任务之后西部 314来到了楼兰古城的西部。 相传很久以前这片土地上(比楼兰古城还早)生活着两个部落一个部落崇拜尖刀(V)一个部落崇拜铁锹(∧)他们分别用 V 和 ∧ 的形状来代表各自部落的图腾。 西部 314 在楼兰古城的下面发现了一幅巨大的壁画壁画上被标记出了 n 个点经测量发现这 n 个点的水平位置和竖直位置是两两不同的。 西部 314认为这幅壁画所包含的信息与这 n 个点的相对位置有关因此不妨设坐标分别为 (1,y1),(2,y2),…,(n,yn)其中 y1∼yn是 11到 n 的一个排列。 西部 314314 打算研究这幅壁画中包含着多少个图腾。 如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤ijk≤n 且 yiyj,yjyk则称这三个点构成 V 图腾; 如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤ijk≤n 且 yiyj,yjyk则称这三个点构成 ∧ 图腾; 西部 314想知道这 n个点中两个部落图腾的数目。 因此你需要编写一个程序来求出 V 的个数和 ∧ 的个数。 输入格式 第一行一个数 n。 第二行是 n 个数分别代表 y1y2,…,yn。 输出格式 两个数中间用空格隔开依次为 V 的个数和 ∧ 的个数。 数据范围 对于所有数据n≤200000且输出答案不会超过64。 1∼ 是 1 到 n 的一个排列。 输入样例 5
1 5 3 2 4输出样例 3 4 代码
#includeiostream
#includecstdio
#includestring
#includecstring
#includestring.h
#includealgorithm
#includecmath
#includevector
#includequeue
#includestack
#includemap
#includeset
#includeunordered_map
#define int long long
using namespace std;
typedef pairint,int PII;
const int N 2e5 10;
int n,a[N],tr[N],Greater[N],lower[N];
int lowbit(int x){return x -x;
}
void add(int x,int c){for(int i x;i n;i lowbit(i))tr[i] c;
}
int sum(int x){int res 0;for(int i x;i;i - lowbit(i))res tr[i];return res;
}
signed main(){cin n;for(int i 1;i n;i ){cin a[i];}for(int i 1;i n;i ){int y a[i];Greater[i] sum(n) - sum(y);lower[i] sum(y-1);add(y,1);}memset(tr,0,sizeof tr);int res1 0,res2 0;for(int i n;i;i --){int y a[i];res1 Greater[i]*(sum(n) - sum(y));res2 lower[i]*(sum(y-1));add(y,1);}cout res1 res2 ;
} 例题2 给定一个长度为 的数列 以及 条指令每条指令可能是以下两种之一 C l r d表示把 A[l],A[l1],…,A[r]都加上 。Q l r表示询问数列中第∼ 个数的和。 对于每个询问输出一个整数表示答案。 输入格式 第一行两个整数 ,。 第二行 个整数 []。 接下来 行表示 条指令每条指令的格式如题目描述所示。 输出格式 对于每个询问输出一个整数表示答案。 每个答案占一行。 数据范围 1≤,≤105, ||≤10000, |[]|≤109 输入样例 10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4输出样例 4
55
9
15 代码
#includeiostream
#includecstdio
#includestring
#includecstring
#includestring.h
#includealgorithm
#includecmath
#includevector
#includequeue
#includestack
#includemap
#includeset
#includeunordered_map
#define int long long
using namespace std;
typedef pairint,int PII;
const int N 1e5 10;
int n,m;
int a[N],tr[N];
int lowbit(int x){return x -x;
}
void add(int x,int c){for(int i x;i n;i lowbit(i)){tr[i] c;}
}
int sum(int x){int res 0;//记录和for(int i x;i;i - lowbit(i))res tr[i];return res;
}
signed main(){cin n m;for(int i 1;i n;i )cin a[i];for(int i 1;i n;i ){add(i,a[i] - a[i-1]);}while(m --){char c;int l,r,d,x;cin c;if(c C){cin l r d;add(l,d);add(r1,-d);}if(c Q){cin x;cout sum(x) endl;}}return 0;
}
