牛客 - 挑战赛39C 牛牛的等差数列

传送门：牛客 - 挑战赛39C

思路分析

一个等差数列可以分割成多个首项不同公差一样的等差数列
更新的时候分段更新，下放标记的时候也是一样

样例输入

4
1 1 1 1
5
1 1 1 1 0
2 1 1 3
1 1 2 1 1
2 2 2 5
2 1 2 23

样例输出

2
3
6

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
#define int long long
 
namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror=0;
    inline char nc() {
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend) {
            p1=buf;
            pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1) {
                IOerror=1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
    }
    template<class T> inline bool read(T &x) {
        bool sign=0;
        char ch=nc();
        x=0;
        for(; blank(ch); ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    template<class T,class... U>bool read(T& h,U&... t) {
        return read(h)&&read(t...);
    }
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N=2e5+10;
const int mod=3LL*5*7*11*13*17*19*23;

struct node {
    int l,r,mid,len,lazya,lazyd,sum;
} tree[N<<2];
 
int s[N];
 
void pp(int x) {
    tree[x].sum=(tree[rs].sum+tree[ls].sum)%mod;
}
 
int cal(int a,int d,int len) {
    return (a*len%mod+(len*(len-1)/2)*d%mod)%mod;
}
 
void build(int x,int l,int r) {
    tree[x]= {l,r,l+r>>1,r-l+1,0,0,0};
    if(l==r) {
        tree[x].sum=s[l]%mod;
        return ;
    }
    int mid=tree[x].mid;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pp(x);
}
 
void pd(int x) {
    int la=tree[x].lazya;
    int ld=tree[x].lazyd;
    if(!la && !ld) return ;
    tree[ls].lazya=(tree[ls].lazya+la)%mod;
    tree[ls].lazyd=(tree[ls].lazyd+ld)%mod;
    int mid=tree[x].mid;
    tree[rs].lazya=(tree[rs].lazya+la+tree[ls].len*ld%mod)%mod;
    tree[rs].lazyd=(tree[rs].lazyd+ld)%mod;
    tree[ls].sum=(tree[ls].sum+cal(la,ld,tree[ls].len))%mod;
    tree[rs].sum=(tree[rs].sum+cal(la+tree[ls].len*ld%mod,ld,tree[rs].len))%mod;
    tree[x].lazya=0;
    tree[x].lazyd=0;
}
 
void modify(int x,int l,int r,int a,int d) {
    if(l<=tree[x].l&&tree[x].r<=r) {
        tree[x].sum=(tree[x].sum+cal(a,d,tree[x].len))%mod;
        tree[x].lazya=(tree[x].lazya+a)%mod;
        tree[x].lazyd=(tree[x].lazyd+d)%mod;
        return ;
    }
    pd(x);
    int mid=tree[x].mid;
    if(r<=mid) modify(ls,l,r,a,d);
    else if(l>mid) {
        modify(rs,l,r,a,d);
    } else {
        modify(ls,l,mid,a,d);
        modify(rs,mid+1,r,(a+(mid-l+1)*d%mod)%mod,d);
    }
    pp(x);
}
 
int query(int x,int l,int r) {
    if(l<=tree[x].l&&tree[x].r<=r) {
        return tree[x].sum;
    }
    pd(x);
    int mid=tree[x].mid;
    int ans=0;
    if(l<=mid) ans=(ans+query(ls,l,r))%mod;
    if(r>mid) ans=(ans+query(rs,l,r))%mod;
    return ans;
}
 
signed main() {
 
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
 
    int n;
    read(n);
    for(int i=1; i<=n; i++) read(s[i]);
    build(1,1,n);
    int q;
    read(q);
    while(q--) {
        int op,l,r,val,d;
        read(op,l,r,val);
        if(op==1) {
            read(d);
            modify(1,l,r,val%mod,d%mod);
        } else {
            printf("%lld\n",query(1,l,r)%val);
        }
    }
 
 
 
 
 
    return 0;
}