#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
typedef pair<int, int> PII;
typedef pair<string,int> PSI;
#define f first
#define s second
#define pb push_back
const int N = 1e5+10;
int n,p,m;
int w[N];
struct node
{
int l,r;
int sum,add,mul;
}tr[N*4];
void pushup(int u)
{
tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%p;
}
void eval(node &t,int add,int mul)
{
t.sum=(t.sum*mul+(t.r-t.l+1)*add)%p;
t.mul=t.mul*mul%p;
t.add=(t.add*mul+add)%p;
}
void pushdown(int u)
{
eval(tr[u<<1],tr[u].add,tr[u].mul);
eval(tr[u<<1|1],tr[u].add,tr[u].mul);
tr[u].add=0,tr[u].mul=1;
}
void build(int u,int l,int r)
{
if(l==r) tr[u]={l,r,w[r],0,1};
else
{
tr[u]={l,r,0,0,1};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int l,int r,int add,int mul)
{
if(tr[u].l>=l && tr[u].r<=r) eval(tr[u],add,mul);
else
{
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u<<1,l,r,add,mul);
if(r>mid) modify(u<<1|1,l,r,add,mul);
pushup(u);
}
}
int query(int u,int l,int r)
{
if(tr[u].l>=l && tr[u].r<=r) return tr[u].sum;
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
int sum=0;
if(l<=mid) sum=query(u<<1,l,r);
if(r>mid) sum=(sum+query(u<<1|1,l,r))%p;
return sum;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>p;
for(int i=1;i<=n;i++) cin>>w[i];
build(1,1,n);
cin>>m;
while (m -- )
{
int t,l,r,d;
cin>>t>>l>>r;
if(t==1)
{
cin>>d;
modify(1,l,r,0,d);
}
else if(t==2)
{
cin>>d;
modify(1,l,r,d,1);
}
else cout<<query(1,l,r)<<endl;
}
return 0;
}
活动打卡代码
AcWing 1277. 维护序列
活动打卡代码
AcWing 247. 亚特兰蒂斯
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
struct Segment
{
double x,y1,y2;
int k;
bool operator<(const Segment &t)const
{
return x<t.x;
}
}seg[N*2];
struct node
{
int l,r;
int cnt;
double len;
}tr[N*8];
vector<double>ys;
int find(double y)
{
return lower_bound(ys.begin(),ys.end(),y)-ys.begin();
}
void pushup(int u)
{
if(tr[u].cnt) tr[u].len=ys[tr[u].r+1]-ys[tr[u].l];
else if(tr[u].l!=tr[u].r)
{
tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
}
else tr[u].len=0;
}
void build(int u,int l,int r)
{
tr[u]={l,r,0,0};
if(l!=r)
{
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
}
void modify(int u,int l,int r,int k)
{
if(tr[u].l>=l && tr[u].r<=r)
{
tr[u].cnt+=k;
pushup(u);
}
else
{
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u<<1,l,r,k);
if(r>mid) modify(u<<1|1,l,r,k);
pushup(u);
}
}
int main()
{
int t=1;
while(cin>>n&&n)
{
ys.clear();
for(int i=0,j=0;i<n;i++)
{
double x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
seg[j++]={x1,y1,y2,1};
seg[j++]={x2,y1,y2,-1};
ys.push_back(y1),ys.push_back(y2);
}
sort(ys.begin(),ys.end());
ys.erase(unique(ys.begin(),ys.end()),ys.end());
build(1,0,ys.size()-2);
sort(seg,seg+n*2);
double res=0;
for(int i=0;i<n*2;i++)
{
if(i) res+=tr[1].len*(seg[i].x-seg[i-1].x);
modify(1,find(seg[i].y1),find(seg[i].y2)-1,seg[i].k);
}
printf("Test case #%d\n", t++);
printf("Total explored area: %.2lf\n\n",res);
}
}
活动打卡代码
AcWing 243. 一个简单的整数问题2
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
typedef pair<int, int> PII;
typedef pair<string,int> PSI;
#define f first
#define s second
#define pb push_back
const int N = 1e5+10;
int n,m;
int w[N];
struct node
{
int l,r;
int sum,add;
}tr[N*4];
void pushup(int u)
{
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u)
{
auto &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
if(root.add)
{
left.add+=root.add,left.sum+=(left.r-left.l+1)*root.add;
right.add+=root.add,right.sum+=(right.r-right.l+1)*root.add;
root.add=0;
}
}
void build(int u,int l,int r)
{
if(l==r) tr[u]={l,r,w[r],0};
else
{
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int l,int r,int d)
{
if(tr[u].l>=l && tr[u].r<=r)
{
tr[u].sum+=(tr[u].r-tr[u].l+1)*d;
tr[u].add+=d;
}
else
{
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u<<1,l,r,d);
if(r>mid) modify(u<<1|1,l,r,d);
pushup(u);
}
}
int query(int u,int l,int r)
{
if(tr[u].l>=l && tr[u].r<=r) return tr[u].sum;
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
int sum=0;
if(l<=mid) sum=query(u<<1,l,r);
if(r>mid) sum+=query(u<<1|1,l,r);
return sum;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];
build(1,1,n);
char op[2];
int l,r,d;
while (m -- )
{
cin>>op>>l>>r;
if(*op=='C')
{
cin>>d;
modify(1,l,r,d);
}
else cout<<query(1,l,r)<<endl;
}
return 0;
}
活动打卡代码
AcWing 246. 区间最大公约数
区间gcd=gcd(a[l],gcd(a[l+1],a[r]),a[l+1]~a[r]用差分去求
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
typedef pair<int, int> PII;
typedef pair<string,int> PSI;
#define f first
#define s second
#define pb push_back
const int N = 5e5+10;
int n,m;
int w[N];
struct node
{
int l,r;
int sum,d;//差分，gcd
}tr[N*4];
int gcd(int a, int b) // 欧几里得算法
{
return b ? gcd(b, a % b) : a;
}
void pushup(node &u,node &l,node &r)
{
u.sum=l.sum+r.sum;
u.d=gcd(l.d,r.d);
}
void pushup(int u)
{
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r)
{
if(l==r)
{
int b=w[r]-w[r-1];
tr[u]={l,r,b,b};
}
else
{
tr[u].l=l,tr[u].r=r;
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int x,int v)
{
if(tr[u].l==x && tr[u].r==x)
{
int b=tr[u].sum+v;
tr[u]={x,x,b,b};
}
else
{
int mid=tr[u].l+tr[u].r>>1;
if(x<=mid) modify(u<<1,x,v);
else modify(u<<1|1,x,v);
pushup(u);
}
}
node query(int u,int l,int r)
{
if(l>r) return {0};
if(tr[u].l>=l && tr[u].r<=r) return tr[u];
else
{
int mid=tr[u].l+tr[u].r>>1;
if(r<=mid) return query(u<<1,l,r);
else if(l>mid) return query(u<<1|1,l,r);
else
{
auto left=query(u<<1,l,r);
auto right=query(u<<1|1,l,r);
node res;
pushup(res,left,right);
return res;
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];
build(1,1,n);
int l,r;
int d;
char op[2];
while (m -- )
{
cin>>op>>l>>r;
if(*op=='Q')
{
auto left=query(1,1,l);
auto right=query(1,l+1,r);
cout<<abs(gcd(left.sum,right.d))<<endl;
}
else
{
cin>>d;
modify(1,l,d);
if(r+1<=n) modify(1,r+1,-d);
}
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
typedef pair<int, int> PII;
typedef pair<string,int> PSI;
#define f first
#define s second
#define pb push_back
const int N = 1e5+10;
int n,m;
int tr1[N],tr2[N];
int a[N];
int lowbit(int x)
{
return x&-x;
}
void add(int tr[],int x,int c)
{
for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}
int ask(int tr[],int x)
{
int res=0;
for(int i=x;i;i-=lowbit(i)) res+=tr[i];
return res;
}
int rb(int x)
{
return ask(tr1,x)*(x+1)-ask(tr2,x);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{
int b=a[i]-a[i-1];
add(tr1,i,b);
add(tr2,i,i*b);
}
while(m--)
{
string op;
int l,r,d;
cin>>op;
if(op=="C")
{
cin>>l>>r>>d;
add(tr1,l,d),add(tr2,l,l*d);
add(tr1,r+1,-d),add(tr2,r+1,-d*(r+1));
}
else
{
cin>>l>>r;
cout<<rb(r)-rb(l-1)<<endl;
}
}
return 0;
}
