树状数组是大家很熟悉的数据结构了吧！不明白的话自己手动学习。作者要好好复习树状数组了。
ps：点击每道题目名称可跳转至题目网页。
easy（简单模板）：
简单单点加法+求和操作。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define maxn 500001
using namespace std;
inline int read(){
int x=0;bool f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=0;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
if(f) return x;
return 0-x;
}
int n,m;
int tree[maxn<<1];
int lowbit(int x){return x & -x;}
void add(int x,int k){
for(int i=x;i<=n;i+=lowbit(i)) tree[i]+=k;
}
int sum(int x){
int res=0;
for(int i=x;i>0;i-=lowbit(i)) res+=tree[i];
return res;
}
int main(){
n=read(),m=read();
int i,x,y,p;
for(i=1;i<=n;i++) add(i,read());
for(i=1;i<=m;i++){
p=read(),x=read(),y=read();
if(p==1) add(x,y);
else printf("%d
",sum(y)-sum(x-1));
}
return 0;
}
这题跟下面一题类似，因此略。
简单区间加法+求和操作。
这题用线段树的做法当然是废话，但树状数组的做法需要应用一点数学知识：差分。
额，以前写过注释了，现在直接贴上来。
/*
（很有趣的数学呵呵～）
设置b[i]=a[i]-a[i-1]，则有等式：
a[1]+a[2]+...+a[n]
= (b[1]) + (b[1]+b[2]) + ... + (b[1]+b[2]+...+b[n])
= n*b[1] + (n-1)*b[2] +... + b[n]
= n*(b[1]+b[2]+...+b[n]) - (0*b[1]+1*b[2]+...+(n-1)*b[n])
所以我们就维护一个数组c[n]，其中c[i] = (i-1)*b[i]，每当修改b的时候，就同步修改一下c，这样复杂度就不会改变。那么原式 = n*sigma(b,n) - sigma(c,n)//sigma(b,n)表示b数组前n个数的和（时间复杂度为log2(n)）
这里便可以上代码了：
*/
#include<bits/stdc++.h>
#define maxn 100005
#define ll long long
using namespace std;
ll a[maxn],b[maxn],c[maxn],n,m;
int read(){
int x=0;bool f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
if(!f) return 0-x;
return x;
}
void update(ll *x,ll k,ll num)
{
while(k<=n){
x[k]+=num;
k+=k&-k;
}
}
ll query(ll *x,ll k)
{
ll sum=0;
while(k){sum+=x[k]; k-=k&-k;}
return sum;
}
int main()
{
n=read(),m=read();
for(ll i=1;i<=n;i++){a[i]=read();update(b,i,a[i]-a[i-1]);update(c,i,(i-1)*(a[i]-a[i-1]));}
while(m--)
{
ll x,y,z=read(),q;
if(z==1){
x=read(),y=read(),q=read();
update(b,x,q);update(b,y+1,-q);
update(c,x,q*(x-1));update(c,y+1,-q*y);
}
else{
x=read();y=read();
printf("%lld
",y*query(b,y) - query(c,y) - (x-1)*query(b,x-1) + query(c,x-1));
}
}
return 0;
}
medium（小试牛刀）：
额，我真想吐槽一下用归并排序写逆序对的常数真是大到爆炸，于是来一发树状数组吧。
思路：将给的n个数分别捆绑上它们在原序列的位置（可以用struct捆），然后将这些数从大到小排序，从大到小（重点！）依次将每个数的值离散化，然后按照原序列从前往后的顺序将每个数离散化后的值插入树状数组的对应位置。
离散化是因为输入的数有可能很大（10^9？），数组开不下那么多位，而最多只有4W个数，因此离散化后就只需要给树状数组开4W位了。
不难证明其正确性——树状数组中对第x位的查询求的是第1-x位的和，由于是按照原序列从前往后的顺序插入值，先插入树状数组的值的位置一定在后插入树状数组的值的位置的前面。如果先插入的数比后插入的数大，那这两个数就能组成逆序对了。
有人可能会问：树状数组查询的是前缀和，也就是之前插入的 比当前数小的数 的个数，怎么能查询出 比当前数大的数 的个数呢？
呃，你是不是没明白上面红字标的那句话？“从大到小依次将每个数的值离散化”这句话的实际操作看这个例子（10 8 6 4 4的每位不是离散化成4 3 2 1 1，而是1 2 3 4 4）。
这样原序列就变成了反序的，这时树状数组看似查询的是之前插入的 比当前数小的数 的个数，实际上之前那些“比当前数小的数”都是在反序离散化后形成的，它们原本的值是比当前数大的。 再加上那些数的位置在当前数前面，那些数就都能和当前数组成逆序对了。
因此对于每一个后插入的数，设这个数在原序列是第x位，求一下树状数组中第1~x位的和（简单query操作）即可求出所有 位置在这个数（第x位）前面且原数比当前数在原序列中的数大的数 的数量了。最后总数量就是原序列的总逆序对数。
另外，上面只是理论可行的做法，实际上逆序对的定义是 i<j 且 ai>aj（不是ai>=aj），而对于每一个插入的数，树状数组的query操作求得是第1~x位的和，算上了之前插入的等于当前这个数的数，为了把它们去掉，实际查询的时候可以让query只求第1 ~ x-1位的和，这样即可避免将两个相同的数算为逆序对。
当然如果您有强迫症，您可以查询第1~x位的和，只不过要多写两行代码把那些相同的数多查询出的答案减掉。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,tot,tree[100010],d[100010];
long long ans;
struct node{
int val,id;
bool operator<(const node&a)const{
return val>a.val;
}
}a[100010];
int lowbit(int x){return x&-x;}
void add(int o,int x){
for(;o<=n;o+=lowbit(o)) tree[o]+=x;
}
int query(int x){
int sum=0;
for(;x>0;x-=lowbit(x)) sum+=tree[x];
return sum;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i].val);
a[i].id=i;
}
sort(a+1,a+n+1);
//离散化
d[a[1].id]=++tot;
for(int i=2;i<=n;i++){
if(a[i].val!=a[i-1].val) ++tot; //要设相同的数在同一位置
d[a[i].id]=tot;
}
for(int i=1;i<=n;i++){
add(d[i],1);
ans+=query(d[i]-1);
}
printf("%lld",ans);
return 0;
}
2.弱点
这道题所在的oj要花钱才能注册账号看题……因此我贴题目吧。
Description
一队勇士正在向你进攻，每名勇士都有一个战斗值ai。但是这队勇士却有一个致命弱点，如果存在i<j<k使得ai>aj>ak，则会影响他们整体的战斗力。我们将这样的一组(i,j,k)称为这队勇士的一个弱点。请求出这队勇士的弱点数目。
Input
输入的第一行是一个整数n，表示勇士的数目。
接下来一行包括n个整数，表示每个勇士的战斗值ai。
Output
输出为一行，包含一个整数。表示这队勇士的弱点数目。
Sample Input
4
10 8 3 1
Sample Output
4
HINT
对于30%的数据，3<=n<=100
对于100%的数据，3<=n<=1000000
对于100%的数据，1<=ai<=1000000，每个ai均不相同
三维逆序对，很明显跟上一题做法相似。那怎么搬运呢？我们可以基于三维逆序对的中间元素考虑。
思路：既然能用树状数组求第x个数能和第1 ~ x-1个数组成多少逆序对，那肯定也能求第x个数能和第x+1 ~ n个数组成多少逆序对，不过由于树状数组只能用来求前缀和，因此我们可以把后者理解为求第x个数能和第x+1 ~ n个数组成多少反向同序对（大家都理解同序对吧？逆序对的反义词，即满足 i<j 且 ai<aj 的二元组(i,j)，反向同序对即为将序列反过来后满足 i<j 且 ai<aj 的二元组，对于原序列就是满足 i>j 且 ai<aj 的二元组，反反得正，与逆序对同义），这样就可以通过把序列反过来求同序对个数来求第x个数能和第x+1 ~ n个数组成多少逆序对了。根据乘法原理，把两侧能组逆序对的数量相乘，就得到了以第x个数为中间元素的三维逆序对个数。将以每个数为中间元素的三维逆序对个数相加就是总三维逆序对个数咯。
tip：我写代码的时候为了省事，依然做了从大到小和从小到大的离散化（从小到大的离散化），实际上这道题题面标明了ai不会超过10^6，数组开得下，而且每个ai互不相同，这说明离散化的去重效果就没用了，因此完全可以不用离散化，反序嘛直接把 1000001-ai 的值插入树状数组就行了。
#include<cstdio>
#include<iostream>
#include<algorithm>
#define maxn 1000001
#define LL long long
using namespace std;
const int BufferSize=1; //由于read中是使用Getchar一位一位地读，数据项的个数为1
char buffer[BufferSize],*head,*tail;
int len;
inline char Getchar(){
if(head==tail){
len=fread(buffer,1,BufferSize,stdin);
tail=(head=buffer)+len;
}
return *head++;
}
inline int read(){
int x=0,f=1;char c=Getchar();
for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=Getchar()) x=x*10+c-'0';
return x*f;
}
inline void put(int x){
int num=0; char c[20];
while(x) c[++num]=(x%10)+'0', x/=10;
while(num) putchar(c[num--]);
putchar('
');
}
int n,tot,rtot,tree[maxn],rtree[maxn],d[maxn],rd[maxn]; //不带r的是用来求第x个数能和第1~x-1个数组成多少逆序对，带r的是用来求第x个数能和第x+1~n个数组成多少逆序对
LL ans[maxn],rans[maxn],res;
struct node{
int val,id;
bool operator<(const node&a)const{
return val>a.val;
}
}a[maxn];
inline int lowbit(int x){return x&-x;}
inline void add(int *t,int o,int x){
for(;o<=n;o+=lowbit(o)) t[o]+=x;
}
inline LL query(int *t,int x){
LL sum=0;
for(;x>0;x-=lowbit(x)) sum+=t[x];
return sum;
}
int main(){
n=read();
int i;
for(i=1;i<=n;i++){a[i].val=read(); a[i].id=i;}
sort(a+1,a+n+1);
//先从大到小，后从小到大离散化一次
d[a[1].id]=++tot, rd[a[n].id]=++rtot;
for(i=2;i<=n;i++){
if(a[i].val!=a[i-1].val) ++tot;
d[a[i].id]=tot;
if(a[n-i+1].val!=a[n-i+2].val) ++rtot;
rd[a[n-i+1].id]=rtot;
}
for(i=1;i<=n;i++){
add(tree,d[i],1);
ans[i]=query(tree,d[i]-1);
add(rtree,rd[n-i+1],1);
rans[n-i+1]=query(rtree,rd[n-i+1]-1);
}
for(i=1;i<=n;i++) res+=ans[i]*rans[i];
printf("%lld
",res);
return 0;
}
这题明显可以用树状数组打。
思路：
由于每个数可能很大，数组开不下，我们依然把所有数离散化，不过这不是逆序对，要从小到大离散化。树状数组 tree[i] 表示离散化后的数 i 为当前第几小数，将对于每个数x，对树状数组第x位进行add操作+1即可，表示它占了一个排名，这样比x大的数都要往后排一名。
比如序列：5 3 7 9 1
离散化后：3 2 4 5 1
插入第1个数3后，第i位对应的query(i)：0 0 1 1 1 （query(i)操作在逆序对题中已经讲过，表示求树状数组第1~i位的和）
插入第2个数2后，第i位对应的query(i)：0 1 2 2 2
插入第3个数4后，第i位对应的query(i)：0 1 2 3 3
插入第4个数5后，第i位对应的query(i)：0 1 2 3 4
插入第5个数1后，第i位对应的query(i)：1 2 3 4 5
相信大家都知道初始序列中的数离散化后的排名是不变的，因此离散化后的数第几小，在原序列中对应的数也是第几小。因此这样做肯定是可行的。
还有一个小问题：怎么查询？
相信大家都注意到query(i)序列是单调不下降的，因此可以使用二分快速查找。那查找几呢？根据题目，我们要求前1，3，5，……个数的中位数。假设我们要求前 i 个数的中位数，根据求和公式，第(i+1)/2小的数就是中位数。所以只要寻找最小的 id 使 query(id) = (i+1)/2就行了。这个位置 id 表示的其实是原序列一个数离散化后的数，因此我们把它对应回去，输出它原来的数就行咯。
#include<bits/stdc++.h>
#define maxn 100001
using namespace std;
inline int read(){
int x=0; bool f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=0; c=getchar();}
while(isdigit(c)){x=x*10+c-'0'; c=getchar();}
if(!f) return 0-x;
return x;
}
int n,tree[maxn],lsh[maxn],rlsh[maxn],tot; //lsh[i]表示原序列中第i个数离散化后的值，rlsh[i]（reverse lsh）数组用来存储离散化后的值i对应的原序列中的数
struct node{
int val,id;
bool operator<(const node &a)const{
return val<a.val;
}
}a[maxn];
inline int lowbit(int x){return x&-x;}
inline void add(int x,int v){
for(;x<=n;x+=lowbit(x)) tree[x]+=v;
}
inline int query(int x){
int res=0;
for(;x>0;x-=lowbit(x)) res+=tree[x];
return res;
}
int binary(int x){ //二分
int l=1,r=tot,mid;
while(l<r){
mid=(l+r)>>1;
if(query(mid)>=x) r=mid;
else l=mid+1;
}
return l;
}
int main(){
n=read();
int i;
for(i=1;i<=n;i++) a[i].val=read(), a[i].id=i;
sort(a+1,a+n+1);
lsh[a[1].id]=++tot;
rlsh[tot]=a[1].val;
for(i=2;i<=n;i++){
if(a[i].val!=a[i-1].val) tot++;
lsh[a[i].id]=tot;
rlsh[tot]=a[i].val;
}
for(i=1;i<=n;i++){
add(lsh[i],1);
if(i&1) printf("%d
",rlsh[binary((i+1)/2)]);
}
return 0;
}
这道题用树状数组做的时间复杂度为O(n log22 n) （二分套query操作，两个的复杂度都是log2级别）
ps：这题方法太多了，有兴趣了解更简单方法的可以看我写的另一篇随笔。
hard（高端应用）：
1.大包子的宠物猎人
OJ依然要钱，贴题。
Description
任务一开始，大包子就发现有些不对劲:这些gc龙竟然会写c++，而且熟练的使用了编译开关-O4使自己换上了一套全新的护甲。作为一名pascal选手大包子不甘示弱，决定顶着巨大的常数压力，去写一个破解gc龙护甲程序。
经过对gc龙短暂的研究之后，大包子发现gc龙们战斗时会排成一列，而gc龙的护甲值其实就是破坏他们护甲的关键。大包子可以用pascal程序对某个区间的gc龙进行hack，如果这个区间内的某个gc龙的护甲值与该区间其他gc龙的护甲值互质，这个gc龙的护甲就会失效，被大包子用太刀砍死。一次hack可以让大包子同时砍死多条gc龙。
于是大包子又开始想这么一个问题：每次hack某一个区间能让大包子砍死几条gc龙呢？相信聪明的读者已经想到了答案，那就把它告诉大包子吧。
Input
第二行有a1，a2，a3...an n个数，第i条gc龙的护甲值
接下来m行，每行两个数l，r，代表询问hack区间[l，r]能让大包子砍死几条龙
Output
Sample Input
10 4
1 2 3 4 5 6 7 8 9 10
1 7
3 6
2 9
4 10
Sample Output
3
1
2
1
这题原题没给数据范围，其实数据范围是1<=n, m<=100000，1<=ai<=100001 （数据范围亲测）。而且这题的测评数据估计有问题，必须要预处理出1~100003的所有质数才行（1~100002就会RE），目前还不知道为啥。
本题思维难度不小，直接从题面入手好像没什么思路。但是大家肯定都发现了这题肯定需要筛素数。那筛素数是干吗用的呢？
思路：
考虑gc龙的护甲值。预处理出所有质数后，将序列中的每个护甲值分解质因数，然后对于每条gc龙，在左右侧分别找 距其最近的 护甲值有公共质因数的 gc龙 的位置，对它们分别连一条边（edge，我在这里只是作习惯称呼）。这样当hack一个区间 [l，r] 时，对于这条gc龙，只要判断它左右连接的数是否都不在 [l，r] 区间即可判断这条gc龙的护甲值是否与区间其它gc龙的护甲值都互质了（因为如果最近的护甲值不互质的gc龙都不在查询区间 [l，r] 里的话，这条gc龙的护甲值肯定就和区间里其它龙的都互质了）。
但是这样肯定不够，因为n、m高达10W，对于m个询问都遍历一遍 [l，r] 区间肯定超时。那怎么办？用树状数组！
这里的树状数组 tree[i] 用来记录区间 [1，i] 内的边数（即左端点和右端点都在区间内的边）。对于每组查询区间 [l，r]，将所有右端点小于等于 r 的边的左端点插入树状数组的对应位置，那么query(r)-query(l-1)就能求出区间 [l，r]的边数了。
所以我们先把所有的边按照右端点从小到大进行排序，然后把所有要查询的区间也按照右端点从小到大进行排序。
排序原因：我们要对所有区间离线查询。为什么不在线查询？很简单，如果在线按照输入顺序现算答案的话，会发现将区间内的边的信息插入树状数组的话复杂度还是很高，很难入手优化。如果将两者都按照右端点从小到大进行排序，设一个右端点大的区间为r，右端点小的区间r’（不用考虑它们的左端点），那么query(r)的答案一定包含（大于等于）query(r')（因为树状数组查询的是前缀和，而我们只根据右端点的大小判断是否插入左端点，右端点越大，就能插入越多的左端点）。
综上我们就衍生出了一种带优化的查询：按照查询区间右端点从小到大的顺序，并按照边的右端点从小到大的顺序依次将边的左端点插入树状数组。当边的右端点大于区间的右端点时，做一轮query操作查询答案。然后到后面右端点更大的区间，接着从这条边开始将左端点插入树状数组，并当边的右端点大于区间的右端点时查询答案，以此类推。
上述方法利用树状数组的求前缀和的特性，将边的插入在线性时间内完成，避免了多次清空树状数组及重新插入，将时间复杂度优化到了O(n log2 n) ~ O(n2)之间。
由于一条gc龙只要向左连的边和向右连的边中有一个在查询区间内 就说明它的护甲值与区间内其它gc龙的护甲值有不互质的（也就是hack不死），因此对于向左连的边和向右连的边，分别做一下“带优化的查询”，就能把所有hack不死的龙的数量求出来了。
但是这样一做又有一个问题：如果一条gc龙向左连的边和向右连的边都在区间内，那这条龙gc就会被算两次，因此我们介入除 向左连的边 和 向右连的边 之外的第3种边：把一条gc龙 向左连的边的端点 和 向右连的边的端点 相连，再做一次“带优化的查询”，得出的答案就是向左连的边和向右连的边都在区间内的gc龙的数量，从hack不死的龙的数量中减掉这个多余的答案就可以了。
好像还忘了说一个事情，就是如果一条gc龙左边没有任何gc龙与其在护甲值上有公共质因数，它向左连的边的端点就设为0（由于是否将左端点插入树状数组是根据边的右端点大小判断的，0有可能被插入树状数组的对应位，也就是树状数组的第0位，而树状数组是不能对第0位进行操作的，因此在树状数组的所有操作（add，query）开头把代入的 位置i 加1，避免对第0位进行操作）；如果一条gc龙右边没有任何gc龙与其在护甲值上有公共质因数，它向右连的边的端点就设为inf（右端点是用来判断是否在查询区间 [l，r] 内的，不会插入树状数组，因此不用特殊调整树状数组的操作）。
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
return x*f;
}
const int N=100003,inf=0x7f7f7f7f;
int n,m,tmp,a[N],tree[N],pre[N],sub[N],p[N],last[2*N],ans[3][N];
//p[0]存储素数个数，p[1~?]用来存储素数（筛）
bool ck[2*N];
struct segment{
int l,r,id;
bool operator < (const segment &x) const{
return r<x.r;
}
}q[N];
bool cmp(segment a,segment b){
return a.id<b.id;
}
vector<segment> seg[3]; //建3个树状数组
inline int lowbit(int x){
return x&(-x);
}
inline void add(int i){
i++; //+1原因：左端点有可能是0（即一条gc龙左边没有与它有公共质因数的gc龙，它的左连边值默认为0）
for(;i<=n;i+=lowbit(i)) tree[i]++;
}
inline int sum(int i){
i++; //同line28
int ret=0;
for(;i>0;i-=lowbit(i)) ret+=tree[i];
return ret;
}
inline int query(int l,int r){
return sum(r)-sum(l-1);
}
void calc(int md){ //用来快速查找区间内有多少条边
memset(tree,0,sizeof(tree));
for(int i=1,j=0;i<=m;i++){ //按照右端点从小到大依次遍历每个区间，这样后面的区间可以覆盖前面的区间，方便树状数组依次查询，节省时间复杂度
for(;j<n && seg[md][j].r<=q[i].r; j++) //当连边右端点没有超过区间右端点时把左端点插入树状数组，由于右端点一定在左端点右边，因此只要最后查询区间内的左端点，右端点也一定是在区间内的
add(seg[md][j].l); //将边的左端点加入树状数组
ans[md][q[i].id]=query(q[i].l,q[i].r); //查询区间内有多少个左端点->有多少条gc龙与其它龙有连边
}
}
int main(){
int i,j,maxn;
n=read(),m=read();
for(i=2;i<=N;i++){ //欧拉筛素数
if(!ck[i]) p[++p[0]]=i;
for(j=1;j<=p[0] && i*p[j]<=N;j++){
ck[i*p[j]]=1;
if(i%p[j]==0) break;
}
}
for(i=1;i<=n;i++){ //分解质因数，并链接有共同质因数的gc龙
a[i]=read();
tmp=a[i]; //备份护甲值，用来分解质因数
maxn=0;
for(j=1;p[j]<=tmp;j++){
if(tmp%p[j]==0){ //可以分解出这个质因数
maxn=max(maxn,last[p[j]]); //最后要得到上一个分解出与其共有的质因数的gc龙编号
last[p[j]]=i; //记录本次分解出这个质因数的gc龙编号
while(tmp%p[j]==0) tmp/=p[j]; //把这个质因数除干净
}
}
pre[i]=maxn;//记录prevent数组，链接上一条 分解出与其共有的质因数的 gc龙
}
memset(last,127,sizeof(last));
for(i=n;i>=1;i--){ //倒序做一遍分解质因数，并反向链接有共同质因数的gc龙。**向右连的边必须单用一个循环做，向左连到的最近gc龙向右连到的最近gc龙不一定是自己。例如：9（3*3）往左连到6（3*2），但6向右连到8（4*2）。
tmp=a[i];
maxn=inf;
for(j=1;p[j]<=tmp;j++){
if(tmp%p[j]==0){
maxn=min(maxn,last[p[j]]);
last[p[j]]=i;
while(tmp%p[j]==0) tmp/=p[j];
}
}
sub[i]=maxn;
}
for(int i=1;i<=n;i++){ //将有共同质因数的相近gc龙依次链接
seg[0].push_back((segment){pre[i],sub[i]});
seg[1].push_back((segment){pre[i],i});
seg[2].push_back((segment){i,sub[i]});
}
sort(seg[0].begin(),seg[0].end()); //按照右端点给边排序
sort(seg[1].begin(),seg[1].end());
sort(seg[2].begin(),seg[2].end());
for(int i=1;i<=m;i++){
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i; //将每个区间绑定上编号，方便最后还原顺序
}
sort(q+1,q+m+1); //将区间按照右端点排序
calc(0);
calc(1);
calc(2);
sort(q+1,q+m+1,cmp); //将区间恢复成原顺序
for(int i=1;i<=m;i++)
printf("%d
",q[i].r-q[i].l+1-(ans[1][i]+ans[2][i]-ans[0][i])); //q[i].r-q[i].l+1表示区间内有多少条gc龙
return 0;
}
最快的一次跑了918ms，挺慢的，主要是这种方法只是在查询上（calc函数）做了小优化，但由于输入的数字不确定，gc龙之间连的边数也不确定。但是可以证明对于3种边，每种边的边数不会超过大约n条（简单证明：讨论所有向左连的边的情况，每条gc龙只会对最近的一只连边，最坏情况下除最左边的gc龙以外，所有gc龙都能在左边找到与其护甲值有公共质因数的gc龙并连边，即使这样也只有n-1条向左连的边。对于其它2种边同理），且随机数据下连边一般都较少，因此查询的时间复杂度介于O(n log2 n) ~ O(n2)之间。程序中的其它部分（如筛素数、排序）等的时间复杂度都是O(n log2 n)级别的，因此总时间复杂度仍介于O(n log2 n) ~ O(n2)之间。
2.列方阵 （您是不是觉得很熟悉Ah）
noip2017 提高组d2t3，看这篇即可http://www.cnblogs.com/scx2015noip-as-php/p/noip2017.html
额，一周时间细搞树状数组真的很值么……不管啦，就先这样扒！