题目概述

Ayano and sequences

解题报告

其实并不是很难，但感觉考场上性价比不高 🤔 ，也可能只是我们队做的太慢了 😭 。

这个问题如果在线做会发现涉及到时间和区间两个维度，并不是很好做（主席树也许可行？），不如直接考虑离线。

用ODT维护 $a$ 相同的区间，在加入区间 $[L,R,w]$ 时记录操作时间 $lt$ ，若该区间在第 $rt$ 个操作时被删除，说明 $[lt,rt-1]$ 这些操作都影响到了区间 $[L,R]$ ，并且区间的 $a$ 值都是 $w$ ，在 $lt-1$ 和 $rt-1$ 分别记录 $-1$ 和 $+1$ 进行差分。

然后只要对操作顺序进行扫描线，问题显然转化成了一个前缀和问题，可以用线段树维护。

我用了一种通用的矩阵方法求这个前缀和，但实际上这题并不用这么麻烦……可以直接通过 $w$ 乘上时间来完成前缀和操作，所以也可以树状数组区间修改来做。

示例程序

#include<set>
#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;
typedef unsigned long long ULL;
const int maxn=500000,maxm=500000,maxt=maxn<<2;

int n,m;
struct node{
    int L,R,c,t;
    node(int l=0,int r=0,int w=0,int T=0) {L=l;R=r;c=w;t=T;}
    bool operator < (const node &a) const {return L<a.L;}
};
typedef set<node>::iterator SI;
set<node> S;SI it,l,r;
int tp[maxm+5],L[maxm+5],R[maxm+5],W[maxm+5];
struct DATA {int c,L,R,f;};
vector<DATA> q[maxm+5];
ULL len[maxt+5],sum[maxt+5],pre[maxt+5],tag[maxt+5][3];
ULL ans[maxn+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[1<<16],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,1<<16,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
struct fastO{
    int si;char buf[1<<16];
    fastO() {si=0;}
    void putc(char ch){
        if (si==(1<<16)) fwrite(buf,1,si,stdout),si=0;
        buf[si++]=ch;
    }
    ~fastO() {fwrite(buf,1,si,stdout);}
}fo;
#define putc fo.putc
template<typename T> void writei(T x,char ch='\n'){
    static int len=0,buf[100];
    if (x<0) putc('-'),x=-x;
    do buf[len++]=x%10,x/=10; while (x);
    while (len) putc(buf[--len]+48);
    if (ch) putc(ch);
}
SI Erase(SI it,int t){
    if (it->t<t){
        q[it->t-1].push_back(DATA{it->c,it->L,it->R,-1});
        q[t-1].push_back(DATA{it->c,it->L,it->R,1});
    }
    return S.erase(it);
}
inline SI Node(int x) {return prev(S.upper_bound(node(x,1e9)));}
SI Split(int x,int t){
    if (x>n) return S.end();
    it=Node(x);if (it->L==x) return it;
    int L=it->L,R=it->R,c=it->c;
    Erase(it,t);S.insert(node(L,x-1,c,t));
    return S.insert(node(x,R,c,t)).first;
}
void Assign(int L,int R,int c,int t){
    r=Split(R+1,t);l=Split(L,t);
    for (it=l;it!=S.end() && it->R<=R;it=Erase(it,t));
    S.insert(node(L,R,c,t));
}
void Build(int l,int r,int p=1){
    len[p]=r-l+1;
    if (l==r) return;
    int mid=l+(r-l>>1);
    Build(l,mid,p<<1);Build(mid+1,r,p<<1|1);
}
inline void Addtag(int p,ULL a,ULL b,ULL c){
    pre[p]+=len[p]*b+sum[p]*c;
    sum[p]+=len[p]*a;
    tag[p][1]+=tag[p][0]*c+b;
    tag[p][0]+=a;
    tag[p][2]+=c;
}
void Pushdown(int p){
    ULL a=tag[p][0],b=tag[p][1],c=tag[p][2];
    if (a || b || c){
        Addtag(p<<1,a,b,c);Addtag(p<<1|1,a,b,c);
        tag[p][0]=tag[p][1]=tag[p][2]=0;
    }
}
void Insert(int L,int R,int k,int l=1,int r=n,int p=1){
    if (L==l && r==R) return Addtag(p,k,k,1);
    int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) Insert(L,R,k,l,mid,p<<1); else if (L>mid) Insert(L,R,k,mid+1,r,p<<1|1);
    else Insert(L,mid,k,l,mid,p<<1),Insert(mid+1,R,k,mid+1,r,p<<1|1);
    sum[p]=sum[p<<1]+sum[p<<1|1];
    pre[p]=pre[p<<1]+pre[p<<1|1];
}
ULL Ask(int L,int R,int l=1,int r=n,int p=1){
    if (L==l && r==R) return pre[p];
    int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) return Ask(L,R,l,mid,p<<1); else if (L>mid) return Ask(L,R,mid+1,r,p<<1|1);
    else return Ask(L,mid,l,mid,p<<1)+Ask(mid+1,R,mid+1,r,p<<1|1);
}
int main(){
    readi(n);readi(m);
    for (int i=1,x;i<=n;i++) readi(x),S.insert(node(i,i,x,1));
    for (int i=1;i<=m;i++){
        readi(tp[i]);readi(L[i]);readi(R[i]);readi(W[i]);
        if (tp[i]==1) Assign(L[i],R[i],W[i],i);
    }
    for (auto x:S){
        q[x.t-1].push_back(DATA{x.c,x.L,x.R,-1});
        q[m].push_back(DATA{x.c,x.L,x.R,1});
    }
    Build(1,n);
    for (int i=1;i<=m;i++){
        if (tp[i]==2){
            Insert(L[i],R[i],W[i]);
            if (1<L[i]) Insert(1,L[i]-1,0);
            if (R[i]<n) Insert(R[i]+1,n,0);
        } else Addtag(1,0,0,1);
        for (auto x:q[i]) ans[x.c]+=Ask(x.L,x.R)*x.f;
    }
    for (int i=1;i<=n;i++) writei(ans[i],i<n?' ':'\n');
    return 0;
}