解题报告 P4198 楼房重建

题目内容

P4198

大意:维护一串序列,单点修改,在线查询 LIS

解题思路

首先这题要注意精度问题,有可能会出现玄学的精度错误

分析题意:考虑看到的楼房最高点 (i,H_i),不难发现能看到的楼房的最高点的斜率都是递增的,即 k_i=i/H_i 满足单调递增(这应该很好想)。发现大区间的信息可以由小区间合并而来,可以使用线段树。这里的单点修改很简单,主要的难点在于如何在 pushup 时合并子区间的信息。

l_k 维护线段树下标为 k 代表的区间中能被看见的楼房的个数(就是单纯只考虑这个区间),m_k 维护 k 区间中楼房的最大斜率。

考虑我们正在处理一个区间,线段树对应的下标为 k ,已经递归处理完他的左半边 L 和右半边 R,现在在进行合并。m_k=\max(m_L,m_R),这个是非常好想的,k 区间的最大斜率就是左右两半边取 max。问题就是 l_k 怎么合并,他不能单纯的等于 l_L+l_R,因为可能会出现右区间中的楼房被左区间的楼房挡住的情况,因此不能直接加起来。

很明显,我们需要在 R 区间中寻找有多少楼房不会被左边挡住。令 f(mk,k) 为在区间 k 中第一个不被 mk 斜率挡住的楼房及此楼房后面看得到的楼房的总数。返回之前的合并过程,有 l_k=l_L+f(m_L,R),因为 L 区间的贡献是无论如何都会产生的。故要在 R 中查找以第一个不会被左区间挡到的楼房开始的能看见的最多的楼房数。

现在考虑正在处理 f ,进入了 R 区间,而 R 区间又由两个小的区间 R_1R_2 构成。以下分三种情况:

  • 如果 m_R,说明左区间会把右区间全部挡完,返回 0
  • 如果 R 区间长度为 1,则看这栋楼是否会被挡,如果不会,返回 1,反之返回 0
  • 如果 m_{R_1},即右区间的左子区间会被挡完,那么就不管左区间了,递归查询右区间即 f(mk,R_2)
  • 如果 m_{R_1} > mk,即左子区间不会被挡完,那么显然右子区间产生的贡献即为 m_{R}-m_{R_2},即右区间的总个数(是已经处理完了的)减去左区间的贡献。然后还要递归查询左区间,因为不知道挡了多少,即 f(mk,R_1)

上述 pushup 过程的核心代码如下(f2 为上文的 mf1 为上文的 l):

int pushup(double mk,int i,int j,int k)
{
    if(f2[k]<=mk)//挡完
        return 0;
    if(a[i]>mk)//如果第一栋楼都能被看见
        return f1[k];//说明可以直接返回这个区间计算过的答案
    if(i==j)//区间长度为1的情况
        return f2[k]>mk;
    if(f2[L]<=mk)//如果左区间挡完
        return pushup(mk,M+1,j,R);//递归查询右区间
    return pushup(mk,i,M,L)+f1[k]-f1[L];//否则递归查询左区间再加上右区间的贡献
}

void change(int i,int j,int x,double d,int k)
{
    // balabala
    f2[k]=max(f2[L],f2[R]);
    f1[k]=f1[L]+pushup(f2[L],M+1,j,R);//左的全部贡献加上右还没被挡完的部分
    return;
}

了解了以上要点之后,不难发现每一次 pushup 的操作都为 O(\log n),故总复杂度为 O(m\log^2n)

代码:

#include <cstdio>
#include <cctype>
#include <algorithm>
#define L (k<<1)
#define R (L|1)
#define M ((i+j)>>1)

using std::max;

const int maxn=1e5+5;

int f1[maxn<<2],n,m;
double f2[maxn<<2];//维护最大斜率的线段树
double a[maxn];//存储每栋楼的斜率

//快读省略

int pushup(double mk,int i,int j,int k)
{
    if(f2[k]<=mk)
        return 0;
    if(a[i]>mk)
        return f1[k];
    if(i==j)
        return f2[k]>mk;
    if(f2[L]<=mk)
        return pushup(mk,M+1,j,R);
    return pushup(mk,i,M,L)+f1[k]-f1[L];
}


void modify(int i,int j,int x,double d,int k)
{
    if(i==j&&i==x)
    {
        f1[k]=1;
        f2[k]=d;
        return;
    }
    if(x<=M)
        modify(i,M,x,d,L);
    if(x>M)
        modify(M+1,j,x,d,R);
    f2[k]=max(f2[L],f2[R]);
    f1[k]=f1[L]+pushup(f2[L],M+1,j,R);
    return;
}

int main()
{
    n=read(),m=read();
    int x,y;
    for(int i=1;i<=m;i++)
    {
        x=read(),y=read();
        a[x]=(double)y/(double)x;
        modify(1,n,x,a[x],1);
        printf("%d\n",f1[1]);
    }
    return 0;
}

解题报告 P4868 Preprefix sum

题目内容

P4868

大意:维护一串序列,支持单点修改和前前缀和查询(\displaystyle\sum_{k=1}^i\sum_{j=1}^ka_j

解题思路

前前缀和,就是前缀和的前缀和,既然需要查询前前缀和,那么就可以想到维护序列的前缀和,查询的时候区间查询 [1,i],修改的时候由于修改一个特定位置的数,后面的所有前缀和都会被影响,所以相当于区间修改前缀和,区间修改区间查询,很容易想到使用线段树维护。

当然用差分处理了的树状数组也可以,但是线段树明显好理解。

要注意的细节:

  • 建线段树的时候记得是记录前缀和
  • 修改 a_ix 的时候相当于 (i,n] 的前缀和都要加上 x-a_i,所以 a_i 一定要存下来

代码:

#include <cstdio>
#include <cctype>
#define L (k<<1)
#define R (L|1)
#define M ((i+j)>>1)
typedef long long ll;

const int maxn=100005;
ll a[maxn],s[maxn],f[maxn<<2],tag[maxn<<2];

int n,m;

inline ll read()
{
    char c = getchar();
    ll s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

void build(int i,int j,int k)
{
    if(i==j)
    {
        a[i]=read();
        s[i]=s[i-1]+a[i];
        f[k]=s[i];
        return;
    }
    build(i,M,L);
    build(M+1,j,R);
    f[k]=f[L]+f[R];
    return;
}

inline void down(int i,int j,int k)
{
    f[L]+=tag[k]*(M-i+1ll);
    f[R]+=tag[k]*(ll)(j-M);
    tag[L]+=tag[k];
    tag[R]+=tag[k];
    tag[k]=0;
    return;
}

void modify(int i,int j,int l,int r,int k,int d)
{
    if(i>=l && j<=r)
    {
        f[k]+=d*(j-i+1ll);
        tag[k]+=d;
        return;
    }
    if(tag[k])
        down(i,j,k);
    if(l<=M)
        modify(i,M,l,r,L,d);
    if(r>M)
        modify(M+1,j,l,r,R,d);
    f[k]=f[L]+f[R];
    return;
}

ll ask(int i,int j,int l,int r,int k)
{
    if(i>=l && j<=r)
        return f[k];
    if(tag[k])
        down(i,j,k);
    ll ans=0;
    if(l<=M)
        ans+=ask(i,M,l,r,L);
    if(r>M)
        ans+=ask(M+1,j,l,r,R);
    return ans;
}

int main()
{
    n=read(),m=read();
    build(1,n,1);
    char opt[10];
    int i;
    while(m--)
    {
        scanf("%s %d",opt,&i);
        if(opt[0]=='M')
        {
            ll x=read();
            modify(1,n,i,n,1,x-a[i]);
            a[i]=x;
        }
        else
            printf("%lld\n",ask(1,n,1,i,1));
    }
    return 0;
}

解题报告 P5524 [Ynoi2012]NOIP2015洋溢着希望

题目内容

P5524

大意:维护一个序列 a,使其支持以下操作:

  • 给定 lr,求 \displaystyle\sum_{i=l}^r\sin(a_i)
  • 给定 lrv,让 [l,r] 中的每一个数加 v

解题思路

终于有一道我可以做的 Ynoi 了 qwqwq

最简单的 Ynoi,没有之一,像我这种只会线段树的 sb 都可以切了它 qwq

观察这题,发现要求维护的是 \sum\sin(a_i),而我们需要进行区间加某数的操作,所以考虑对 \sum\sin(a_i+v) 进行展开:

\begin{aligned}
&\sum_{i=l}^r\sin(a_i+v)\
=&\sum_{i=l}^r(\sin a_i\cos v+\sin v\cos a_i)\
=&\cos v\sum_{i=l}^r\sin a_i+\sin v\sum_{i=l}^r\cos a_i
\end{aligned}

所以我们需要维护两棵线段树,一棵维护 \sum\sin a_i,一棵维护 \sum\cos a_i,而涉及到 \sum\cos a_i 的修改怎么办呢?见下

\begin{aligned}
&\sum_{i=l}^r\cos(a_i+v)\
=&\sum_{i=l}^r(\cos a_i\cos v-\sin a_i\sin v)\
=&\cos v\sum_{i=l}^r\cos a_i-\sin v\sum_{i=l}^r\sin a_i
\end{aligned}

所以两个要同时修改,要建立临时变量来存储之前的 \sum\sin a_i\sum\cos a_i。然后为了优化常数不被卡,每次修改的时候要预处理 \sin v\cos v,不然会被卡。

lazytag 要开 long long,不然在玄学的在 line 几万处 WA

#include <cstdio>
#include <cctype>
#include <cmath>
#define L (k<<1)
#define R (L|1)
#define M (i+j>>1)
typedef long long ll;

const int maxn=2e5+5;
double fsin[maxn<<2],fcos[maxn<<2];
int n,m;
ll tag[maxn<<2];

inline ll read()
{
    char c=getchar();
    ll s=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
        s=10*s+c-'0',c=getchar();
    return s;
}

void build(int i,int j,int k)
{
    if(i==j)
    {
        int x=read();
        fsin[k]=sin(x);
        fcos[k]=cos(x);
        return;
    }
    build(i,M,L);
    build(M+1,j,R);
    fsin[k]=fsin[L]+fsin[R];
    fcos[k]=fcos[L]+fcos[R];
    return;
}

void down(int i,int j,int k)
{
    double lsin=fsin[L],rsin=fsin[R],lcos=fcos[L],rcos=fcos[R];
    double sine=sin(tag[k]),cosi=cos(tag[k]);
    fsin[L]=lsin*cosi+lcos*sine;
    fcos[L]=lcos*cosi-lsin*sine;
    tag[L]+=tag[k];
    fsin[R]=rsin*cosi+rcos*sine;
    fcos[R]=rcos*cosi-rsin*sine;
    tag[R]+=tag[k];
    tag[k]=0;
    return;
}

void modify(int i,int j,int l,int r,int k,int d)
{
    if(i>=l && j<=r)
    {
        double ssin=fsin[k],ccos=fcos[k];
        double sine=sin(d),cosi=cos(d);
        fsin[k]=ssin*cosi+ccos*sine;
        fcos[k]=ccos*cosi-ssin*sine;
        tag[k]+=d;
        return;
    }
    if(tag[k])
        down(i,j,k);
    if(l<=M)
        modify(i,M,l,r,L,d);
    if(r>M)
        modify(M+1,j,l,r,R,d);
    fsin[k]=fsin[L]+fsin[R];
    fcos[k]=fcos[L]+fcos[R];
    return;
}

double ask(int i,int j,int l,int r,int k)
{
    if(i>=l && j<=r)
        return fsin[k];
    if(tag[k])
        down(i,j,k);
    double ans=0;
    if(l<=M)
        ans+=ask(i,M,l,r,L);
    if(r>M)
        ans+=ask(M+1,j,l,r,R);
    return ans;
}

int main()
{
    n=read();
    build(1,n,1);
    m=read();
    int t,l,r,v;
    while(m--)
    {
        t=read(),l=read(),r=read();
        if(t==1)
        {
            v=read();
            modify(1,n,l,r,1,v);
        }
        else
            printf("%.1f\n",ask(1,n,l,r,1));
    }
    return 0;
}

解题报告 P1438 无聊的数列

题目内容

P1438

大意:维护一个序列,支持区间加等差数列以及单点查询操作

解题思路

注意等数列:等差数列的差分是相等的,所以我们可以维护一个原数列的差分,每一次加等差数列的时候进行区间加公差以及两端点修改就可以了:

假设要加上去的数列首项为 K,公差为 D,要加上去的区间为 [l,r]p 为原序列的差分,则有 p_l\leftarrow Kp_{[l+1,r]}\leftarrow p_{[l+1,r]}+D,至于最后一项,肯定是要还原回去的原来加了多少现在就要还回去多少,所以 p_{r+1}\leftarrow p_{r+1}-K-(r-l)D

  • 注意如果 r=n 的话不能进行最后一个操作
  • 注意如果 l=r 的话不能进行第二个操作

除此之外坑点就没有了,观察 p 数组,我们要进行的是区间修改和区间查询工作,所以线段树可以解决这个问题(虽然树状数组也可以),代码如下:

#include <cstdio>
#include <cctype>
#define L (k<<1)
#define R (L|1)
#define M (i+j>>1)

const int maxn=1e5+5;
int f[maxn<<2],tag[maxn<<2],a[maxn],n,m;

inline int read()
{
    bool w=0;
    int x=0;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            w=1;
        c=getchar();
    }
    while(isdigit(c))
        x=x*10+c-'0',c=getchar();
    return w?-x:x;
}

void build(int i,int j,int k)
{
    if(i==j)
    {
        a[i]=read();
        f[k]=a[i]-a[i-1];
        return;
    }
    build(i,M,L);
    build(M+1,j,R);
    f[k]=f[L]+f[R];
    return;
}

void down(int i,int j,int k)
{
    f[L]+=tag[k]*(M-i+1);
    f[R]+=tag[k]*(j-M);
    tag[L]+=tag[k],tag[R]+=tag[k];
    tag[k]=0;
    return;
}

void modify(int i,int j,int l,int r,int k,int d)
{
    if(i>=l && j<=r)
    {
        f[k]+=(j-i+1)*d;
        tag[k]+=d;
        return;
    }
    if(tag[k])
        down(i,j,k);
    if(l<=M)
        modify(i,M,l,r,L,d);
    if(r>M)
        modify(M+1,j,l,r,R,d);
    f[k]=f[L]+f[R];
    return;
}

int ask(int i,int j,int l,int r,int k)
{
    if(i>=l && j<=r)
        return f[k];
    if(tag[k])
        down(i,j,k);
    int ans=0;
    if(l<=M)
        ans+=ask(i,M,l,r,L);
    if(r>M)
        ans+=ask(M+1,j,l,r,R);
    return ans;
}


int main()
{
    n=read(),m=read();
    build(1,n,1);
    int opt,l,r,k,d,p;
    while(m--)
    {
        opt=read();
        if(opt==1)
        {
            l=read(),r=read(),k=read(),d=read();
            modify(1,n,l,l,1,k);
            if(l+1<=r)
                modify(1,n,l+1,r,1,d);
            if(r<n)
                modify(1,n,r+1,r+1,1,-((r-l)*d+k));
        }
        else
        {
            p=read();
            printf("%d\n",ask(1,n,1,p,1));
        }
    }
    return 0;
}

解题报告 P1471 方差

题目内容

P1471

大意:维护一段实数序列,使之支持区间加一个数以及区间平均值和方差的查询

解题思路

平均值的求解非常好想,只需要将区间和除以区间长度即可,但是方差呢?如何维护?先考虑将方差的式子进行展开:

\begin{aligned}
s^2&=\frac{\sum_{i=1}^n(x_i-\bar x)^2}{n}\
&=\frac{\sum_{i=1}^n(x_i^2-2x_i\bar x+\bar x^2)}{n}\
&=\frac{\sum_{i=1}^nx_i^2-2\bar x\sum_{i=1}^nx_i+n\bar x^2}{n}\
\because&\frac{\sum_{i=1}^nx_i}n=\bar x\
s^2&=\frac{\sum_{i=1}^nx_i^2}n-\bar x^2
\end{aligned}

所以我们需要维护两棵线段树,分别是维护 \sum x_i\sum x_i^2,但当我们涉及到区间修改的时候呢?维护平方和的线段树怎么搞?见下:

假设要加上去的数为 d

\begin{aligned}
&\sum_{i=1}^n(x_i+d)^2\
=&\sum_{i=1}^n(x_i^2+2x_id+d^2)\
=&\sum_{i=1}^nx_i^2+2d\sum_{i=1}^nx_i+nd^2
\end{aligned}

对比原来的式子,发现要加上去的是 \displaystyle2d\sum_{i=1}^nx_i+nd^2,注意到这里的 \sum x_i 是修改前的,所以修改的时候要先修改平方和,再修改另一个

然后这题我式子推错一次,pushdown 写挂一次,看来要多练线段树了,代码里面还有一些要注意的东西:

  • 注意所有的数字都是实数,建议使用关闭流同步的 cin
  • 每次更新线段树的时候要同时更新两个
  • 别把式子抄错

顺便吐槽这个数据里面的浮点数的表现形式,简直令人kfjdljahtiojfeawruiofklnvd

然后就差不多了,代码见下:

#include <iostream>
#include <iomanip>
#include <cmath>
#define L (k<<1)
#define R (L|1)
#define M (i+j>>1)
using namespace std;

const int maxn=1e5+5;
int n,m;
double f1[maxn<<2],f2[maxn<<2],tag[maxn<<2];

void build(int i,int j,int k)
{
    if(i==j)
    {
        cin>>f1[k];
        f2[k]=f1[k]*f1[k];
        return;
    }
    build(i,M,L);
    build(M+1,j,R);
    f1[k]=f1[L]+f1[R];
    f2[k]=f2[L]+f2[R];
    return;
}

void down(int i,int j,int k)
{
    int l1=M-i+1,l2=j-M;
    f2[L]+=2.0*tag[k]*f1[L]+l1*tag[k]*tag[k];
    f2[R]+=2.0*tag[k]*f1[R]+l2*tag[k]*tag[k];
    f1[L]+=tag[k]*l1;
    f1[R]+=tag[k]*l2;
    tag[L]+=tag[k],tag[R]+=tag[k];
    tag[k]=0;
    return;
}

void modify(int i,int j,int l,int r,int k,double d)
{
    if(i>=l && j<=r)
    {
        f2[k]+=2.0*d*f1[k]+(j-i+1)*d*d;
        f1[k]+=(j-i+1)*d;
        tag[k]+=d;
        return;
    }
    if(tag[k])
        down(i,j,k);
    if(l<=M)
        modify(i,M,l,r,L,d);
    if(r>M)
        modify(M+1,j,l,r,R,d);
    f1[k]=f1[L]+f1[R];
    f2[k]=f2[L]+f2[R];
    return;
}

double sum1(int i,int j,int l,int r,int k)
{
    if(i>=l && j<=r)
        return f1[k];
    if(tag[k])
        down(i,j,k);
    double ans=0;
    if(l<=M)
        ans+=sum1(i,M,l,r,L);
    if(r>M)
        ans+=sum1(M+1,j,l,r,R);
    return ans;
}

double sum2(int i,int j,int l,int r,int k)
{
    if(i>=l && j<=r)
        return f2[k];
    if(tag[k])
        down(i,j,k);
    double ans=0;
    if(l<=M)
        ans+=sum2(i,M,l,r,L);
    if(r>M)
        ans+=sum2(M+1,j,l,r,R);
    return ans;
}

inline double avr(int l,int r)
{
    return sum1(1,n,l,r,1)/(r-l+1);
}

inline double fangcha(int l,int r)
{
    double avre=avr(l,r),len=r-l+1;
    return sum2(1,n,l,r,1)/len-avre*avre;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    build(1,n,1);
    int t,x,y;
    double k;
    while(m--)
    {
        cin>>t>>x>>y;
        if(t==1)
        {
            cin>>k;
            modify(1,n,x,y,1,k);
        }
        else if(t==2)
            cout<<fixed<<setprecision(4)<<avr(x,y)<<endl;
        else
            cout<<fixed<<setprecision(4)<<fangcha(x,y)<<endl;
    }
}

解题报告 P2574 XOR的艺术

题目内容

P2574

大意:维护一个 0-1 序列,支持区间取反和区间查询 1 的个数的操作

解题思路

使用线段树来维护区间和,依然使用标记,每次取反后该区间的区间和即为区间长度减去原区间和,代码如下:

#include <cstdio>
#define L (k<<1)
#define R (L|1)

const int maxn=2e5+5;
int n,m,tag[maxn<<2],f[maxn<<2];
char s[maxn];

void build(int i,int j,int k)
{
    if(i==j)
    {
        f[k]=s[i]-'0';
        return;
    }
    int m=i+j>>1;
    build(i,m,L);
    build(m+1,j,R);
    f[k]=f[L]+f[R];
    return;
}

void down(int i,int j,int k)
{
    int m=i+j>>1;
    f[L]=m-i+1-f[L];
    f[R]=j-m-f[R];
    tag[L]=!tag[L];
    tag[R]=!tag[R];
    tag[k]=0;
    return;
}

void modify(int i,int j,int l,int r,int k)
{
    if(i>=l && j<=r)
    {
        f[k]=(j-i+1)-f[k];
        tag[k]=!tag[k];
        return;
    }
    if(tag[k])
        down(i,j,k);
    int m=i+j>>1;
    if(l<=m)
        modify(i,m,l,r,L);
    if(r>m)
        modify(m+1,j,l,r,R);
    f[k]=f[L]+f[R];
    return;
}

int ask(int i,int j,int l,int r,int k)
{
    if(i>=l && j<=r)
        return f[k];
    if(tag[k])
        down(i,j,k);
    int m=i+j>>1,ans=0;
    if(l<=m)
        ans+=ask(i,m,l,r,L);
    if(r>m)
        ans+=ask(m+1,j,l,r,R);
    return ans;
}

int main()
{
    scanf("%d %d",&n,&m);
    scanf("%s",s+1);
    build(1,n,1);
    int op,l,r;
    while(m--)
    {
        scanf("%d %d %d",&op,&l,&r);
        if(op)
            printf("%d\n",ask(1,n,l,r,1));
        else
            modify(1,n,l,r,1);
    }
    return 0;
}

解题报告 P4145 上帝造题的七分钟2 / 花神游历各国

题目内容

P4145

大意:维护一个序列,支持两种操作:

  • [l,r] 的每个数开方并向下取整
  • 查询 [l,r] 的区间和

所有数据小于 10^{12} 且都大于 0

解题思路

拿到这道题的时候发现:貌似区间开根没有那么简单,并没有 \sum\sqrt{a_i}=\sqrt{\sum a_i} 这种说法,所以只能很无奈的每次开根都暴力修改。

但是注意所有的数据都大于 0,且有一条很重要的性质是 \sqrt 1=1,所以如果某个区间的和等于这个区间的长度的话,就无需继续往下修改下去了。

注意有一半的点会出现 l>r 的情况,要进行交换!

#include <cstdio>
#include <cmath>
#include <cctype>
#define L (k<<1)
#define R (L|1)
typedef long long ll;

const int maxn=100005;
int n,m;
ll f[maxn<<2];

inline ll read()
{
    bool w=0;
    ll x=0;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            w=1;
        c=getchar();
    }
    while(isdigit(c))
        x=x*10+c-'0',c=getchar();
    return w?-x:x;
}

inline void swap(int &a,int &b)
{
    int t=a;
    a=b;
    b=t;
}

void build(int i,int j,int k)
{
    if(i==j)
    {
        f[k]=read();
        return;
    }
    int m=i+j>>1;
    build(i,m,L);
    build(m+1,j,R);
    f[k]=f[L]+f[R];
    return;
}

void modify(int i,int j,int x,int y,int k)//区间开根
{
    if(i==j && i>=x && j<=y)//如果已经到达叶子节点
    {
        f[k]=sqrt(f[k]);//直接开根
        return;
    }
    if(f[k]==j-i+1)//如果这段区间和等于区间长度
        return;//不管了那就
    int m=i+j>>1;
    if(x<=m)//否则就要继续往下递归修改
        modify(i,m,x,y,L);
    if(y>m)
        modify(m+1,j,x,y,R);
    f[k]=f[L]+f[R];
    return;
}

ll ask(int i,int j,int x,int y,int k)//常规查询操作
{
    if(x<=i && y>=j)
        return f[k];
    ll ans=0;
    int m=i+j>>1;
    if(x<=m)
        ans+=ask(i,m,x,y,L);
    if(y>m)
        ans+=ask(m+1,j,x,y,R);
    return ans;
}

int main()
{
    n=read();
    build(1,n,1);
    m=read();
    int k,l,r;
    while(m--)
    {
        k=read(),l=read(),r=read();
        if(l>r)
            swap(l,r);//交换操作
        if(k)
            printf("%lld\n",ask(1,n,l,r,1));
        else
            modify(1,n,l,r,1);
    }
    return 0;
}

解题报告 P1198 [JSOI2008]最大数

题目内容

P1198

大意:维护一个初始为空的序列,支持以下两种操作:

  • 查询最后 L 个数字中的最大数
  • n+t\bmod D 插入序列末尾,t 为上次查询的答案,初始为 0

解题思路

维护一个带修序列,很容易想到使用维护 RMQ 的线段树来解决问题。

每次查询操作就按照常规来,插入操作就相当于在最后一个位置加上了 n+t\bmod D,至于为什么用 cin 和 cout 是因为使用 scanf 出现了一些玄学错误。代码如下:

#include <iostream>
#define L (k<<1)
#define R (L|1)
typedef long long ll;
using namespace std;

inline ll max(ll a,ll b)
{
    return a>b?a:b;
}

const int maxn=2e5+5;
int m,d,tot;//tot存储当前序列元素个数
ll f[maxn<<2];

ll query(int i,int j,int x,int y,int k)//查询操作
{
    //printf("i:%d,j:%d,x:%d,y:%d,k:%d\n",i,j,x,y,k);
    if(i>=x &&j<=y)
        return f[k];
    int m=i+j>>1;
    ll ans=0;
    if(x<=m)
        ans=max(ans,query(i,m,x,y,L));
    if(y>m)
        ans=max(ans,query(m+1,j,x,y,R));
    return ans;
}

void add(int i,int j,int x,int k,int d)//单点修改操作
{
    if(i==j && i==x)
    {
        f[k]=d;
        return;
    }
    int m=i+j>>1;
    if(x<=m)
        add(i,m,x,L,d);
    else
        add(m+1,j,x,R,d);
    f[k]=max(f[L],f[R]);
    return;
}

int main()
{
    //freopen("1.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>m>>d;
    char c;
    int n=0,t=0;
    for(int i=1;i<=m;i++)
    {
        cin>>c>>n;
        if(c=='Q')
        {
            t=query(1,m,tot-n+1,tot,1);//查询[tot-n+1,tot]
            cout<<t<<endl;
        }
        if(c=='A')
            add(1,m,++tot,1,(n+t)%d);//插入操作
    }
    return 0;
}

解题报告 HDU1754 I HATE IT

题目内容

hdu1754

题意

维护一些学生成绩,支持单点修改和区间求最值操作

解题思路

嗯,造一棵线段树即可

#include <bits/stdc++.h>
#define L (k<<1)
#define R (L|1)
#define M (i+j>>1)
#define f(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int maxn=200000+5;

int a[maxn],f[maxn<<2];

void build(int i,int j,int k)//造树
{
    if(i==j) f[k]=a[i];
    else
    {
        build(i,M,L);
        build(M+1,j,R);
        f[k]=max(f[L],f[R]);
    }
    return;
}

void modify(int u,int d,int i,int j,int k)//单点编辑操作
{
    if(i==j) f[k]=d;
    else
    {
        if(u<=M) modify(u,d,i,M,L);
        if(u>M) modify(u,d,M+1,j,R);
        f[k]=max(f[L],f[R]);//每次操作完记得回溯
    }
    return;
}

int query(int u,int v,int i,int j,int k)//区间查询操作
{
    if(u==i&&v==j) return f[k];
    else
    {
        if(v<=M) return query(u,v,i,M,L);
        if(u>M) return query(u,v,M+1,j,R);
    }
    return max(query(u,M,i,M,L),query(M+1,v,M+1,j,R));
}

int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        memset(a,0,sizeof(a));
        memset(f,0,sizeof(f));
        f(i,1,n) scanf("%d",&a[i]);
        build(1,n,1);
        getchar();//嗯,读入回车符把我坑死了
        f(i,1,m)
        {
            char c;int a,b;
            scanf("%c %d %d\n",&c,&a,&b);//记得读入回车符
            if(c=='U') modify(a,b,1,n,1);
            if(c=='Q') printf("%d\n",query(a,b,1,n,1));
        }
    }
    return 0;
}

反思

tmd这个回车符把我弄得要死不活的
要么使用cin(怎么可能),要么使用getchar()直接读入回车符,要么使用scanf的格式化功能直接把回车符干掉。

然后每组数据读入完之后记得memset即可