A题 原CF 438D The Child and Sequence
题意
给一串数字，m次操作，1.区间查询；2.区间取模；3.单点修改
基本思路
考虑到模如果大于区间的最大值，则取模没有意义。若小于则向下查询并修改，考虑到一个数每次取模最多为原数的\(1/2\)，则可认为修改次数不超过\(\log{2}{n}\)
时间复杂度为\(O(n\log{2}{n}\log{2}{n})\)
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FOR2(i,a,b) for(int i=a;i<=b;i++)
#define sync ios::sync_with_stdio(false);cin.tie(0)
#define ll long long
#define MAXN 100010
using namespace std;
typedef struct{int l,r;ll w,m,laz;
}NODE;NODE nodes[4*MAXN];
int n,m,x,y,op,single,modu,val;
void laztag(int k)
{nodes[k*2].laz+=nodes[k].laz;nodes[k*2+1].laz+=nodes[k].laz;nodes[k*2].w+=nodes[k].laz*(nodes[k*2].r-nodes[k*2].l+1);nodes[k*2+1].w+=nodes[k].laz*(nodes[k*2+1].r-nodes[k*2+1].l+1);nodes[k].laz=0;
}
void build(int l,int r,int k)
{nodes[k].l=l;nodes[k].r=r;nodes[k].laz=0;if(l==r){scanf("%I64d",&nodes[k].w);nodes[k].m=nodes[k].w;return ;}int mid=(l+r)>>1;build(l,mid,k*2);build(mid+1,r,k*2+1);nodes[k].w=nodes[k*2+1].w+nodes[k*2].w;nodes[k].m=max(nodes[k*2+1].m,nodes[k*2].m);
}
ll query(int k)
{ll res=0;if(x<=nodes[k].l&&nodes[k].r<=y){//查询区域完全包含此区间 return nodes[k].w;}if(nodes[k].laz){//laz tag~~laztag(k);}int mid=(nodes[k].l+nodes[k].r)>>1;if(x<=mid) res+=query(k*2);if(y>mid) res+=query(k*2+1);return res;
}
void singleChange(int k)
{if(nodes[k].l==nodes[k].r){nodes[k].w=val;nodes[k].m=val;return;}if(nodes[k].laz){//laz tag~~laztag(k);}int mid=(nodes[k].l+nodes[k].r)>>1;if(single<=mid)singleChange(2*k);else singleChange(2*k+1);nodes[k].w=nodes[2*k].w+nodes[2*k+1].w;nodes[k].m=max(nodes[2*k].m,nodes[2*k+1].m);
}
void partMod(int l,int r,int k)
{if(nodes[k].m<modu){//w<模，没有意义 return;}if(nodes[k].laz){//laz tag~~laztag(k);}if(l==r){nodes[k].w%=modu;nodes[k].m=nodes[k].w;return;}int mid=(nodes[k].l+nodes[k].r)>>1;if(x<=mid)partMod(l,mid,k*2);if(y>mid)partMod(mid+1,r,k*2+1);nodes[k].w=nodes[2*k].w+nodes[2*k+1].w;nodes[k].m=max(nodes[2*k].m,nodes[2*k+1].m);
}int main()
{cin>>n>>m;build(1,n,1);while(m--){cin>>op;if(op==1){//查询 cin>>x>>y;cout<<query(1)<<endl;}if(op==2){//模 cin>>x>>y>>modu;partMod(1,n,1);}if(op==3){//单点修改 cin>>single>>val;singleChange(1);}}return 0;
}B题 原hdu 3047 Multiply game
题意
求区间乘积的值和单点修改
基本思路
和线段树模板题类似
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include<iomanip>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FOR2(i,a,b) for(int i=a;i<=b;i++)
#define sync ios::sync_with_stdio(false);cin.tie(0)
#define ll long long
#define MAXN 60010
#define MOD 1000000007
using namespace std;
typedef struct{int l,r;ll w,laz;
}NODE;NODE nodes[MAXN*4];
ll x,y,n,q,t,single,val;
void build(int l,int r,int k)
{nodes[k].l=l;nodes[k].r=r;if(l==r){scanf("%lld",&nodes[k].w);return ;}int mid=(l+r)>>1;build(l,mid,k<<1);build(mid+1,r,k<<1|1);nodes[k].w=(nodes[k<<1].w*nodes[k<<1|1].w)%MOD;
}
ll query(int l,int r,int k)
{ll res=1;if(x<=l&&r<=y){return nodes[k].w;}int mid=(l+r)>>1;if(x<=mid)res=(res*query(l,mid,k<<1))%MOD;if(y>mid)res=(res*query(mid+1,r,k<<1|1))%MOD;return res;
}
void singleChange(int k)
{if(nodes[k].l==nodes[k].r){nodes[k].w=val;return ;}int mid=(nodes[k].l+nodes[k].r)>>1;if(single<=mid)singleChange(k<<1);else singleChange(k<<1|1);nodes[k].w=(nodes[k<<1].w*nodes[k<<1|1].w)%MOD;
}
int main()
{cin>>t;while(t--){scanf("%lld",&n);build(1,n,1);scanf("%lld",&q);while(q--){int op;scanf("%d",&op);if(op==0){scanf("%lld%lld",&x,&y);printf("%lld\n",query(1,n,1));}if(op){scanf("%lld%lld",&single,&val);singleChange(1); }}}return 0;
}C题 原hdu 4578 Transformation
题意
区间加，区间乘，和区间修改，外加一个查询操作，求\(\sum_{i=l}^r{a_i^p}\)的值。
基本思路
如果沿袭普通操作的话代码可能150行+。
一个思路是使用懒标记标志区间是否均为同一个数，若是，用一个数表示该区间，用于后续计算。若不是，向下查询。
每次都计算某一段相同数的区间,则值为\(\sum_{i=1}^{m}\sum_{j=li}^{ri}{a_i^p}\)
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include<iomanip>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FOR2(i,a,b) for(int i=a;i<=b;i++)
#define sf(f,t) scanf("%f",&t);
#define sync ios::sync_with_stdio(false);cin.tie(0)
#define ll long long
#define INF 0x3f3f3f3f;
#define MAXN 100010
#define MOD 10007
void read(int &x)
{int f=1;x=0;char s=getchar();while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}x*=f;
}
using namespace std;
//区间树更改是耗时最久的操作
typedef struct{int w,laz;
}NODE;NODE nodes[4*MAXN];
int x,y,type,n,m,k,val,p;
inline void laztag(int k)
{if(!nodes[k<<1].laz||!nodes[k<<1|1].laz) nodes[k].laz=0;else if (nodes[k<<1].w!=nodes[k<<1|1].w) nodes[k].laz=0;else {nodes[k].laz=1;nodes[k].w=nodes[k<<1].w;}
}
void update(int l,int r,int k)
{
// cout<<l<<" "<<r<<" "<<k<<endl;if(nodes[k].laz&&x<=l&&r<=y){//区间内元素相同 if(type==1)nodes[k].w=(nodes[k].w+val)%MOD;else if(type==2)nodes[k].w=(nodes[k].w*val)%MOD;else nodes[k].w=val;return;}if(nodes[k].laz){//拆分相同元素的区间为不同元素区间 nodes[k<<1].laz=nodes[k<<1|1].laz=1;nodes[k<<1].w=nodes[k<<1|1].w=nodes[k].w;nodes[k].laz=0;}int mid=(l+r)>>1;if(x<=mid)update(l,mid,k<<1);if(y>mid)update(mid+1,r,k<<1|1);laztag(k);//更新laz
}
ll query(int l,int r,int k)
{if(nodes[k].laz&&x<=l&&r<=y){int res=nodes[k].w;FOR(i,1,val)res=(res*nodes[k].w)%MOD;res=((r-l+1)*res)%MOD;return res;}if(nodes[k].laz){//懒标记下穿 nodes[k<<1].laz=nodes[k<<1|1].laz=1;nodes[k].laz=0;nodes[k<<1].w=nodes[k<<1|1].w=nodes[k].w;}int mid=(l+r)>>1; int res=0;if(x<=mid) res=(res+query(l,mid,k<<1));if(y>mid)res=(res+query(mid+1,r,k<<1|1));return res%MOD;
}int main()
{while(~scanf("%d%d",&n,&m)&&n&&m){FOR2(i,0,4*n){nodes[i].laz=1;nodes[i].w=0;}while(m--){
// scanf("%d%d%d%d",&type,&x,&y,&val);read(type),read(x),read(y),read(val);if(type>=1&&type<=3)update(1,n,1);else printf("%d\n",query(1,n,1)%MOD);}}return 0;
}