敌兵布阵

HDU1166
树状数组即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define lowbit(x) (x&-x)
const int mod=998244353;
const int N=50010;
int a[100100];
int c[100100];
int n;
//a为原数组，c为树状数组，下同
void creat(){for( int i=1;i<=n;i++){c[i]=0;for( int j=0;j<lowbit(i);j++){c[i]+=a[i-j];}}
}
int query( int x){int sum=0;while(x>0){sum+=c[x];x-=lowbit(x);}return sum;
}
void update( int i,int val){while(i<=n){c[i]+=val;i+=lowbit(i);}
}
void solve(){cin>>n;for( int i=1;i<=n;i++){cin>>a[i];}creat();while(1){string s;cin>>s;int x,y;if(s=="Query"){cin>>x>>y;cout<<query(y)-query(x-1)<<endl;}else if(s=="Add"){cin>>x>>y;update(x,y);}else if(s=="Sub"){cin>>x>>y;update(x,-y);}else break;}
}
int main(){
//  ios_base::sync_with_stdio(0);
//  cin.tie(0); cout.tie(0);int t;cin>>t;for( int i=1;i<=t;i++){printf("Case %d:\n",t);solve();}return 0;
}

简单的整数问题

poj3648
分块算法，不写线段树了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100100;
ll a[N];
ll block[350];
ll lz[350];
//lz标记，当执行整块修改时，添加lz标记，代替快修改
int n,m,len;
int get(int x){return x/len;
}
void creat_block( ){for( int i=1;i<=n;i++){block[get(i)]+=a[i];}
}
ll qq( int l,int r){ll res=0;if(get(l)==get(r)){//同一个块内直接暴力for( int i=l;i<=r;i++) res+=a[i]+lz[get(i)];return res;}else {for( int i=l;get(l)==get(i);i++) res+=a[i]+lz[get(i)];//左边不是整块的区间for( int i=get(l)+1;i!=get(r);i++) res+=block[i]+lz[i]*len;for( int i=r;get(i)==get(r);i--) res+=a[i]+lz[get(i)];//右边不是整块的区间}return res;}
void up( int l,int r,int val){if(get(l)==get(r)){for( int i=l;i<=r;i++) a[i]+=val,block[get(i)]+=val;return ;}else {for( int i=l;get(l)==get(i);i++) a[i]+=val,block[get(i)]+=val;for( int i=get(l)+1;i!=get(r);i++) lz[i]+=val;for( int i=r;get(i)==get(r);i--) a[i]+=val,block[get(i)]+=val;}return ;}
int main(){cin>>n>>m;len=sqrt(n);for( int i=1;i<=n;i++){scanf("%lld",&a[i]);}creat_block();for( int i=1;i<=m;i++){char s[2];int x,y;scanf("%s%d%d",s,&x,&y);if(s[0]=='Q'){cout<<qq(x,y)<<endl;}else {int w;scanf("%d",&w);up(x,y,w);}}return 0;
}

数据结构难题

hdu4902
本题使用的解法比较特殊，线段树中没有值，只有懒惰标记，也就是使用懒惰标记充当线段树的值。

当进行更新1时，直接更新懒惰标记即可。
当进行更新2时，如果没有懒惰标记，就直接更新两个子树，如果有懒惰标记，就更新懒惰标记。如果两个子树的懒惰标记相同，更新父节点的懒惰标记。

这种做法看似复杂度过高，不能通过，但是我认为复杂度是合理的，应该为O(nlognloga)
下面是复杂度分析：
首先对于更新1，由于直接更新懒惰标记，复杂度为nlogn
对于更新2，一次更新的最坏复杂度看似为n，整个算法的复杂度看似为n*n，但实际上，由于GCD的性质，每次进行GCD，当前点的数值就会减少一半以上，所以进行loga次操作之后，当前点的数值就会降到1，之后在进行更新时间复杂度就会显著下降。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int  N=100100;
int a[N];
struct node{int l,r,lz;
}tr[N<<2];
void creat(int rt,int l,int r){tr[rt].l=l;tr[rt].r=r;tr[rt].lz=0;if(l==r) {tr[rt].lz=a[l];return;}int mid=(l+r)/2;creat(rt*2,l,mid),creat(rt*2+1,mid+1,r);
}
void pushdown(int rt){if(tr[rt].lz==0) return ;int l=tr[rt].l,r=tr[rt].r;int mid=(l+r)/2;int ln=mid-l+1,rn=r-mid;if(tr[rt].lz!=0){tr[rt*2].lz=tr[rt].lz;tr[rt*2+1].lz=tr[rt].lz;tr[rt*2].lz=tr[rt].lz;tr[rt*2+1].lz=tr[rt].lz;tr[rt].lz=0;}
}
void up_1(int rt,int L,int R,int val){int l=tr[rt].l,r=tr[rt].r;if(L>r||R<l) return ;	if(l==r) {tr[rt].lz=val;return ;}if(l>=L&&r<=R) {int len=r-l+1;tr[rt].lz=val;return ;}pushdown(rt);int mid=(l+r)/2;if(mid>=L) up_1(rt*2,L,R,val);if(mid<R) up_1(rt*2+1,L,R,val);if(tr[rt*2].lz==tr[rt*2+1].lz) tr[rt].lz=tr[rt*2].lz;else tr[rt].lz=0;
}
void up_2( int rt,int L,int R,int x){int l=tr[rt].l,r=tr[rt].r;if(L>r||R<l) return ;	if(l==r) {if(tr[rt].lz>x) tr[rt].lz=__gcd(x,tr[rt].lz);return ;}if(l>=L&&r<=R&&tr[rt].lz!=0) {int len=r-l+1;if(tr[rt].lz>x) tr[rt].lz=__gcd(x,tr[rt].lz);return ;}pushdown(rt);int mid=(l+r)/2;if(mid>=L) up_2(rt*2,L,R,x);if(mid<R) up_2(rt*2+1,L,R,x);if(tr[rt*2].lz==tr[rt*2+1].lz) tr[rt].lz=tr[rt*2].lz;else tr[rt].lz=0;
}
ll qq(int rt,int L,int R){int l=tr[rt].l,r=tr[rt].r;if(l>R||r<L)return 0;if(l==r) return tr[rt].lz;pushdown(rt);if(l>=L&&r<=R) return tr[rt].lz;int mid=(l+r)/2;ll res=0;if(L<=mid) res=qq(rt*2,L,R);if(R>mid) res=qq(rt*2+1,L,R);return res;
}
void solve(){int n;cin>>n;for( int i=1;i<=n;i++) cin>>a[i];creat(1,1,n);int m;cin>>m;for( int i=1;i<=m;i++) {int t,l,r,x;cin>>t>>l>>r>>x;if(t==1) up_1(1,l,r,x);else up_2(1,l,r,x);}for( int i=1;i<=n;i++){cout<<qq(1,i,i)<<" ";}cout<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}