头像

Rain丶bow




离线:18小时前


最近来访(400)
用户头像
烟尘墨
用户头像
天海_1
用户头像
Payxtl
用户头像
小灰灰我是
用户头像
1234abcd
用户头像
StkOvflow
用户头像
yxc的小迷弟
用户头像
stOtue
用户头像
Orreo
用户头像
北海没有WA
用户头像
原神
用户头像
垫底抽風
用户头像
2010
用户头像
骄阳似火
用户头像
潜伏在QQ的微信
用户头像
815741912
用户头像
山海皆可平
用户头像
米卡莎20484
用户头像
微光_74
用户头像
呀呼

活动打卡代码 AcWing 1277. 维护序列

#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 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);
    }
}



#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;
}



区间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;
}


活动打卡代码 AcWing 4729. 解密

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 4728. 乘方

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 3422. 左孩子右兄弟

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 4455. 出行计划

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~