模板&坑点
写下每一个变量名时都请保持头脑清醒，困了就去睡觉
莫队区间要先增大后缩小，要保证区间一直是存在的
普通莫队第二关键字是右端点位置，带修莫队第二关键字是右端点所在块
#include<bits/stdc++.h>
#define N 50004
#define int long long
using namespace std;
int n,m,a[N],bl[N]/*block*/,cnt[N];
struct pnt{
int l,r,bh,ans;
}q[N];
bool cmp(pnt a,pnt b){
if(bl[a.l]==bl[b.l])
return a.r<b.r;
return bl[a.l]<=bl[b.l];
}
bool cmp_bh(pnt a,pnt b){
return a.bh<b.bh;
}
void add(int,int&),del(int,int&);
int gcd(int,int);
void pre();
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i)
scanf("%lld",&a[i]);
pre();
for(int i=1;i<=m;++i){
scanf("%lld%lld",&q[i].l,&q[i].r);
q[i].bh=i;
}
sort(q+1,q+1+m,cmp);
int l=q[1].l,r=l;
for(;r<=q[1].r;++r)
add(a[r],q[1].ans);
--r;
for(int i=2;i<=m;++i){
q[i].ans=q[i-1].ans;
while(l>q[i].l)
add(a[--l],q[i].ans);
while(r<q[i].r)
add(a[++r],q[i].ans);
//先增大后减小！不然cnt可能变成负数
while(l<q[i].l)
del(a[l++],q[i].ans);
while(r>q[i].r)
del(a[r--],q[i].ans);
}
sort(q+1,q+1+m,cmp_bh);
for(int i=1;i<=m;++i){
int p=(q[i].r-q[i].l)*(q[i].r-q[i].l+1),k=gcd(p,q[i].ans);
if(q[i].ans&&q[i].r!=q[i].l)
printf("%lld/%lld\n",q[i].ans/k,p/k);
else
printf("0/1\n");
}
return 0;
}
void add(int k,int &ans){
++cnt[k];
if(cnt[k]>1)
ans+=(cnt[k]<<1)-2;
else
ans+=cnt[k]*cnt[k]-cnt[k];
}
void del(int k,int &ans){
--cnt[k];
ans-=(cnt[k]<<1);
}
void pre(){
int B=(int)sqrt(m);
for(int i=1;i<=n;++i){
bl[i]=i/B;
if(i%B)
++bl[i];
}
}
int gcd(int a,int b){
return !b?a:gcd(b,a%b);
}
线段树叶子节点不能push不然会爆
#include<bits/stdc++.h>
#define N 100005
#define LL long long
using namespace std;
LL L[N<<2],R[N<<2],num[N<<2],tag[N<<2];
LL a[N<<2];
void add(LL,LL,LL,LL),build(LL,LL,LL),sp(LL);
LL sum(LL,LL,LL);
int main(){
LL n,m;
scanf("%lld%lld",&n,&m);
for(LL i=1;i<=n;++i)
scanf("%lld",&a[i]);
build(1,1,n);
for(LL i=1;i<=m;++i){
LL z,x,y; LL k;
scanf("%lld%lld%lld",&z,&x,&y);
if(z&1){
scanf("%lld",&k);
add(1,x,y,k);
}
else
printf("%lld\n",sum(1,x,y));
}
return 0;
}
void build(LL n,LL l,LL r){
L[n]=l,R[n]=r;
if(l==r){
num[n]=a[l];
return ;
}
LL mi=(l+r)>>1;
build(n<<1,l,mi);
build((n<<1)+1,mi+1,r);
num[n]=num[n<<1]+num[(n<<1)+1];
return ;
}
void sp(LL n){
LL l=L[n],r=R[n],mi=(l+r)>>1,k=tag[n];
if(k){
num[n<<1]+=(mi-l+1)*k,tag[n<<1]+=k;
num[(n<<1)+1]+=(r-mi)*k,tag[(n<<1)+1]+=k;
tag[n]=0;
}
return ;
}
void add(LL n,LL x,LL y,LL k){
LL l=L[n],r=R[n];
if(x>r||y<l)
return ;
// 在这里sp(n)的话有可能这个节点是叶子节点，再往下push会炸
if(l>=x&&r<=y){
num[n]+=(r-l+1)*k;
tag[n]+=k;
return ;
}
sp(n);//应该判断完两种范围以后再push
add(n<<1,x,y,k);
add((n<<1)+1,x,y,k);
num[n]=num[n<<1]+num[(n<<1)+1];
}
LL sum(LL n,LL x,LL y){
LL l=L[n],r=R[n];
if(x>r||y<l)
return 0;
if(l>=x&&r<=y)
return num[n];
sp(n);
LL su1=sum(n<<1,x,y);
LL su2=sum((n<<1)+1,x,y);
num[n]=num[n<<1]+num[(n<<1)+1];
return su1+su2;
}记得调用pre函数。
使用++时要注意在同一个函数内部第二次调用被++的元素时，此时该元素是还未+1的。这里第一个bh是已经+1的了，但是第二次调用的bh还是原来的bh。
scanf("%d%d",&re[++bh2].pl,&re[bh2].now);树状数组（单修区查）
#include<bits/stdc++.h>
#define N 500005
using namespace std;
int n,tr[N],m;
void add(int,int);
int qur(int,int);
signed main(){
scanf("%d%d",&n,&m);
for(int i=1,a;i<=n;++i){
scanf("%d",&a);
add(i,a);
}
for(int i=1;i<=m;++i){
int q,x,y;
scanf("%d%d%d",&q,&x,&y);
if(q&1)
add(x,y);
else
printf("%d\n",qur(x-1,y));//这里减去x-1而不是x
}
return 0;
}
void add(int pl,int num){
for(int i=pl;i<=n;i+=(i&(-i)))
tr[i]+=num;
}
int qur(int x,int y){
int ans=0;
for(int i=y;i;i-=(i&(-i))){
ans+=tr[i];
}
for(int i=x;i;i-=(i&(-i)))
ans-=tr[i];
return ans;
}数组a[]的差分数组d[]的第i项为a_i-a_{i-1}
cmp里返回 <= 可能会RE
那种计算数对个数的题，如果有重复元素的话要考虑清楚你的做法能不能保证重复元素对相同元素的贡献是否算到了，如果没有的话，可以通过去重并统计相同元素个数进行额外计算
- P3810 【模板】三维偏序（陌上花开）
动态开点线段树先开点（no=++bh）再判断是否是叶子节点、要不要return。
scanf输入的话记得检查%lld之类的，本地过了交上去可能就寄了
-
赛时尽量用快读快写
写快读时记得先判 a=='-' 再 a=getchar()。
-
用关闭同步流的话记得查一下有没有用scanf或者getchar之类的，会寄。
fhq-treap 记得写 srand(time(0));
关于除法
- 记得检查除数是否为0
在同一个表达式中，对同一个变量既进行读取又进行修改，且没有 “序列点” 分隔时，行为是未定义的，有时候windows跑出来是对的在linux下可能就错了
- 惨案一例
热心网友给的解释：
s[ii-1]=s[ii--]; 显然是不行的，是未定义行为。因为不知道是先算 ii-1 还是先算 ii--。很多企业都禁止使用这种写法，就是语句中提到的变量不能同时自增自减。所以应该改成s[ii-1]=s[ii],--ii;。