首页 > 其他分享 >数据结构练习

数据结构练习

时间：2023-07-06 09:46:55浏览次数：44  
标签：lazy rs int 练习 Tree long Ori 数据结构

数据结构练习

[NOI2021] 密码箱

这么说Quack大爷就有队爷水平了

首先考虑\(f\)是个线性变换

这里对于\(\dfrac{x}{y}\rightarrow \dfrac{y}{x}+a_i\),第\(i\)个元素可以用矩阵表示

\[\left [ \begin{matrix} x& y \\ 0& 0 \\ \end{matrix} \right ] \times\left [ \begin{matrix} a_i& 1 \\ 1& 0 \\ \end{matrix} \right ] \]

于是这里我们可以把序列拉成一个矩阵,但这是不够的,因为原题要对操作序列操作

考虑把每个操作也看作矩阵

对于\(W\),很明显就是左乘

\[\left [ \begin{matrix} 1& 1 \\ 0& 1 \\ \end{matrix} \right ] \]

对于\(E\),手完一下就能发现其实都可以看作减一后在后面填两个数

那其实就相当于左乘

\[\left [ \begin{matrix} 1& 1 \\ 1& 0 \\ \end{matrix} \right ]\times\left [ \begin{matrix} 1& 1 \\ 1& 0 \\ \end{matrix} \right ]\times \left [ \begin{matrix} 1& -1 \\ 0& 1 \\ \end{matrix} \right ]=\left [ \begin{matrix} 2& -1 \\ 1& 0 \\ \end{matrix} \right ] \]

用平衡树维护即可,细节有点多

#include<bits/stdc++.h>
#define ls Tree[p].lc
#define rs Tree[p].rc
using namespace std;
void read(int &x) {
    x = 0;
    int f = 1;
    char s = getchar();
    while (s > '9' || s < '0') {
        if (s == '-')
            f = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + (s - '0');
        s = getchar();
    }
    x *= f;
}
void write(int x) {
    if (x < 0) {
        putchar('-');
        x = (~x) + 1;
    }
    if (x > 9) {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}
const int MOD=998244353;
const int MAXN=2e5+5;
struct Martix{
    int val[2][2];
    void clear()
    {
        memset(val,0,sizeof(val));
    }
    void init()
    {
        clear();
        for(int i=0;i<2;i++)
        {
            val[i][i]=1;
        }
        return;     
    }
    void print()
    {
        for(int i=0;i<2;i++)
        {
            for(int j=0;j<2;j++)
            {
                printf("%d ",val[i][j]);
            }
            printf("\n");
        }
        printf("\n");
    }
    Martix operator*(const Martix x)const{
        Martix Res;
        Res.clear();
        for(int k=0;k<2;k++)
        {
            for(int i=0;i<2;i++)
            {
                for(int j=0;j<2;j++)
                {
                    Res.val[i][j]=((long long)Res.val[i][j]+((long long)val[i][k]*x.val[k][j])%MOD)%MOD;
                }
            }
        }
        return Res;
    }  
}A,B,C;
struct FHQ_node{
    int lc,rc;
    int cnt;
    int Siz;
    int Key;
    Martix dt[2][2],val[2];  
    int lazy_rev;
    int lazy_roll;
};
struct FHQ{
    FHQ_node Tree[MAXN];
    int root;
    int cnt_node;
    int New(int op)
    {
        ++cnt_node;
        Tree[cnt_node].cnt=1;
        Tree[cnt_node].Siz=1;
        Tree[cnt_node].lazy_rev=0;
        Tree[cnt_node].lazy_roll=0;
        Tree[cnt_node].lc=0;
        Tree[cnt_node].rc=0;
        Tree[cnt_node].Key=rand();
        Tree[cnt_node].dt[op][0]=Tree[cnt_node].dt[op][1]=Tree[cnt_node].val[op]=A;
        Tree[cnt_node].dt[op^1][0]=Tree[cnt_node].dt[op^1][1]=Tree[cnt_node].val[op^1]=B;
        return cnt_node;
    }
    void push_up(int p)
    {
        Tree[p].Siz=Tree[ls].Siz+Tree[rs].Siz+Tree[p].cnt;

        Tree[p].dt[0][0].init();
        if(ls)
        {
            Tree[p].dt[0][0]=Tree[p].dt[0][0]*Tree[ls].dt[0][0];
        }    
        Tree[p].dt[0][0]=(Tree[p].dt[0][0]*Tree[p].val[0]);
        if(rs)
        {
            Tree[p].dt[0][0]=Tree[p].dt[0][0]*Tree[rs].dt[0][0];
        }   

        Tree[p].dt[1][0].init();
        if(ls)
        {
            Tree[p].dt[1][0]=Tree[p].dt[1][0]*Tree[ls].dt[1][0];
        }    
        Tree[p].dt[1][0]=(Tree[p].dt[1][0]*Tree[p].val[1]);
        if(rs)
        {
            Tree[p].dt[1][0]=Tree[p].dt[1][0]*Tree[rs].dt[1][0];
        }   

        Tree[p].dt[0][1].init();
        if(rs)
        {
            Tree[p].dt[0][1]=Tree[p].dt[0][1]*Tree[rs].dt[0][1];
        }    
        Tree[p].dt[0][1]=(Tree[p].dt[0][1]*Tree[p].val[0]);
        if(ls)
        {
            Tree[p].dt[0][1]=Tree[p].dt[0][1]*Tree[ls].dt[0][1];
        }  

        Tree[p].dt[1][1].init();
        if(rs)
        {
            Tree[p].dt[1][1]=Tree[p].dt[1][1]*Tree[rs].dt[1][1];
        }    
        Tree[p].dt[1][1]=(Tree[p].dt[1][1]*Tree[p].val[1]);
        if(ls)
        {
            Tree[p].dt[1][1]=Tree[p].dt[1][1]*Tree[ls].dt[1][1];
        }    
    }
    void push_down(int p)
    {
        if(Tree[p].lazy_roll)
        {
            swap(ls,rs);
            swap(Tree[ls].dt[0][0],Tree[ls].dt[0][1]);
            swap(Tree[ls].dt[1][0],Tree[ls].dt[1][1]);
            swap(Tree[rs].dt[0][0],Tree[rs].dt[0][1]);
            swap(Tree[rs].dt[1][0],Tree[rs].dt[1][1]);
            Tree[ls].lazy_roll^=1;
            Tree[rs].lazy_roll^=1;
            Tree[p].lazy_roll=0;
        }
        if(Tree[p].lazy_rev)
        {
            swap(Tree[ls].dt[0][0],Tree[ls].dt[1][0]);
            swap(Tree[ls].dt[0][1],Tree[ls].dt[1][1]);
            swap(Tree[ls].val[0],Tree[ls].val[1]);
            swap(Tree[rs].dt[0][0],Tree[rs].dt[1][0]);
            swap(Tree[rs].dt[0][1],Tree[rs].dt[1][1]);
            swap(Tree[rs].val[0],Tree[rs].val[1]);
            Tree[ls].lazy_rev^=1;
            Tree[rs].lazy_rev^=1;
            Tree[p].lazy_rev=0;
        }
    }
    void Split(int p,int val,int &x,int &y)
	{
		if(!p)
		{
			x=0;
			y=0;
			return;
		}
		push_down(p);
		if(Tree[ls].Siz+Tree[p].cnt<=val)
		{
			x=p;
			Split(rs,val-Tree[ls].Siz-Tree[p].cnt,rs,y);
		}
		else
		{
			y=p;
			Split(ls,val,x,ls);
		}
		push_up(p);
	}
    int Merge(int x,int y)
	{
		if((!x)||(!y))
		{
			return x+y;
		}
		if(Tree[x].Key<Tree[y].Key)
		{
			push_down(x); 
			Tree[x].rc=Merge(Tree[x].rc,y);
			push_up(x);
			return x;
		}
		else
		{
			push_down(y);
			Tree[y].lc=Merge(x,Tree[y].lc);
			push_up(y);
			return y;
		}
	}
    void Insert(int op)
    {
        root=Merge(root,New(op));
        return;
    }
    void Rev(int l,int r)
    {
        int lx,zx,rx;
        Split(root,l-1,lx,rx);
        Split(rx,r-l+1,zx,rx);
        swap(Tree[zx].dt[0][1],Tree[zx].dt[1][1]);
        swap(Tree[zx].dt[0][0],Tree[zx].dt[1][0]);
        swap(Tree[zx].val[0],Tree[zx].val[1]);
        Tree[zx].lazy_rev^=1;
        root=Merge(lx,Merge(zx,rx));
        return;
    }
    void Roll(int l,int r)
    {
        int lx,zx,rx;
        Split(root,l-1,lx,rx);
        Split(rx,r-l+1,zx,rx);
        swap(Tree[zx].dt[0][0],Tree[zx].dt[0][1]);
        swap(Tree[zx].dt[1][0],Tree[zx].dt[1][1]);
        Tree[zx].lazy_roll^=1;
        root=Merge(lx,Merge(zx,rx));
        return;
    }
}tree;
int n,q;
char S[MAXN];
char R[15];
int l,r;

int main()
{
    freopen("code.in","r",stdin);
    freopen("code.out","w",stdout);
    srand(time(0));
    
    A.val[0][0]=1;
    A.val[0][1]=1;
    A.val[1][0]=0;
    A.val[1][1]=1;

    B.val[0][0]=2;
    B.val[0][1]=MOD-1;
    B.val[1][0]=1;
    B.val[1][1]=0;
    
    C.val[0][0]=1;
    C.val[0][1]=1;
    C.val[1][0]=1;
    C.val[1][1]=0;
    read(n);
    read(q);
    scanf("%s",S);
    
    for(int i=0;i<n;i++)
    {
        if(S[i]=='W')
        {
            tree.Insert(0);
        }
        else
        {
            tree.Insert(1);
        }
    }
    printf("%d %d\n",(tree.Tree[tree.root].dt[0][1]*C).val[0][1],(tree.Tree[tree.root].dt[0][1]*C).val[0][0]);
    while(q--)
    {
        scanf("%s",R);
        if(R[0]=='A')
        {
            scanf("%s",R);
            if(R[0]=='W')
            {
                tree.Insert(0);
            }
            else
            {
                tree.Insert(1);
            }
        }
        else if(R[0]=='F')
        {
            read(l);
            read(r);
            tree.Rev(l,r);
        }
        else
        {
            read(l);
            read(r);
            tree.Roll(l,r);
        }
        printf("%d %d\n",(tree.Tree[tree.root].dt[0][1]*C).val[0][1],(tree.Tree[tree.root].dt[0][1]*C).val[0][0]);
    }
}

CF1588F Jumping Through the Array

这个条件看着很奇怪,不妨往分块上想

进一步,考虑操作分块

考虑如果没有操作\(3\),这里我们可以发现涉及到的环只有\(\sqrt n\)

这里我们就可以暴力计算每个操作对每个询问的影响,最后\(\sqrt n\)次暴力推平即可

如果有操作三,我们可以对点染色,可以发现每个交换点的前驱是跟在它一起的

实际上我们可以把它的极长空白前驱放在一起为一个联通块

这里对于操作\(2\)这里我们操作一次大概是直接走前驱,只有\(\sqrt n\)次

然后似乎就完了,注意实现,有点卡常

#include<bits/stdc++.h>
void read(int &x) {
    x = 0;
    int f = 1;
    char s = getchar();
    while (s > '9' || s < '0') {
        if (s == '-')
            f = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + (s - '0');
        s = getchar();
    }
    x *= f;
}
void write(int x) {
    if (x < 0) {
        putchar('-');
        x = (~x) + 1;
    }
    if (x > 9) {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}
using namespace std;
const int MAXN=2e5+5;
int n,q;
long long a[MAXN];
long long sum[MAXN];
int P[MAXN];
int S[MAXN];
int clo[MAXN];
long long Add[MAXN];
struct Query{
    int op,l,r;
    int x,y;
}query[MAXN];
int op,l,r,x,y;
int Rk[1005];
int Tk[MAXN];
int Sz[1005][1005];
int Tot[MAXN];
int main()
{
    //  freopen("date.in","r",stdin);
    //  freopen("date.out","w",stdout);
    scanf("%d",&n);
    int Block=430;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }  
    for(int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=1;i<=n;i++)
    {
        read(P[i]);
        S[P[i]]=i;
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        read(op);
        if(op==1)
        {
            read(l);
            read(r);
            query[i].op=1;
            query[i].l=l;
            query[i].r=r;
        }
        else if(op==2)
        {
            read(x);
            read(y);
            query[i].op=2;
            query[i].x=x;
            query[i].y=y;
        }
        else if(op==3)
        {
            read(x);
            read(y);
            query[i].op=3;
            query[i].x=x;
            query[i].y=y;
        }
    }
    for(int L=1;L<=q;L+=Block)
    {
        int R=min(L+Block-1,q);
        for(int i=0;i<=n;i++)
        {
            clo[i]=0;
            Tk[i]=0;
        }
        for(int i=L;i<=R;i++)
        {
            if(query[i].op==2)
            {
                clo[query[i].x]=query[i].x;
            }
            if(query[i].op==3)
            {
                clo[query[i].x]=query[i].x;
                clo[query[i].y]=query[i].y;
            }
        }
        int cnt_clo=0;

        for(int i=1;i<=n;i++)
        {
            if(clo[i]==i)
            {
                Rk[++cnt_clo]=i;
                int Now=S[i];
                while((!clo[Now]))
                {
                    clo[Now]=i;
                    Now=S[Now];
                }
            }
        }
        int cnt_q=0;
        for(int i=L;i<=R;i++)
        {
            if(query[i].op==1)
            {
                Tk[query[i].l-1]=++cnt_q;
                Tk[query[i].r]=++cnt_q;
            }   
        }
        if(Tk[0])
        {
            for(int i=1;i<=cnt_clo;i++)
            {
                Sz[Tk[0]][i]=0;
            }
        }
        
        for(int i=1;i<=n;i++)
        {
            Tot[clo[i]]++;
            if(Tk[i])
            {
                for(int j=1;j<=cnt_clo;j++)
                {
                    Sz[Tk[i]][j]=Tot[Rk[j]];
                }
            }
        }
        for(int i=L;i<=R;i++)
        {
            if(query[i].op==1)
            {
                l=query[i].l;
                r=query[i].r;
                long long Rp=(sum[r]-sum[l-1]);
                for(int j=1;j<=cnt_clo;j++)
                {
                    int Pl=Sz[Tk[l-1]][j];
                    int Pr=Sz[Tk[r]][j];
                    int Ln=Pr-Pl;
                    Rp=(Rp+((long long)Ln*Add[Rk[j]]));
                }
                printf("%lld\n",Rp);
            }
            else if(query[i].op==2)
            {
                int Now=clo[P[query[i].x]];
                while(1)
                {
                    Add[Now]+=query[i].y;
                    
                    if(Now==clo[query[i].x])
                    {
                        break;
                    }
                    Now=clo[P[Now]];
                }
                
            }
            else
            {
                swap(P[query[i].x],P[query[i].y]);
                S[P[query[i].x]]=query[i].x;
                S[P[query[i].y]]=query[i].y;
            }
        }
        for(int i=1;i<=n;i++)
        {
            a[i]=a[i]+Add[clo[i]];
            sum[i]=sum[i-1]+a[i];
        }
        for(int i=1;i<=n;i++)
        {
            Add[i]=0;
            Rk[min(i,1000)]=0;
            Tot[i]=0;
        }
    }
}

CF679E Bear and Bad Powers of 42

维护每个数到下一个\(42\)次幂的距离

可以发现直接看每次加的是否会超出当前距离的最小值

超出了就暴力改,可以发现每个元素改的次数很少

具体时间复杂度分析就是把线段树每个节点还可以改多少看作势能,可以发现每次会用\(O(1)\)的时间解决\(O(1)\)的势能,而一次赋值只会增加\(O(\log_2(n))\)的势能

注意实现,好像有点卡常

我要做DJ小姐的狗·

#include<bits/stdc++.h>
#define int long long
#define ls 2*p
#define rs 2*p+1
using namespace std;
const int MAXN=1e5+5;
int n,q;
long long a[MAXN];
long long R[MAXN];
int op,l,r,x;
long long B[15];
struct Seg{
    int l,r;
    long long date;
    long long Ori_lazy;
    long long Add;
    long long Ori;
}Tree[MAXN*4];
int get(int x) {
	return *lower_bound(B, B + 12, x) - x;
}
void push_up(int p)
{
    Tree[p].date=min(Tree[ls].date,Tree[rs].date);
}
void push_down(int p)
{
    if(Tree[p].Ori_lazy!=0)
    {
        Tree[ls].Add=0;
        Tree[rs].Add=0;
        Tree[ls].Ori_lazy=Tree[p].Ori_lazy;
        Tree[rs].Ori_lazy=Tree[p].Ori_lazy;
        Tree[ls].date=get(Tree[p].Ori_lazy);
        Tree[rs].date=get(Tree[p].Ori_lazy);
        Tree[ls].Ori=Tree[p].Ori_lazy;
        Tree[rs].Ori=Tree[p].Ori_lazy;
        Tree[p].Ori_lazy=0;
    }
    if(Tree[p].Add!=0)
    {
        Tree[ls].date-=Tree[p].Add;
        Tree[ls].Ori+=Tree[p].Add;
        if(Tree[ls].Ori_lazy!=0)
        {
            Tree[ls].Ori_lazy+=Tree[p].Add;
        }
        else
        {
            Tree[ls].Add+=Tree[p].Add;            
        }


        Tree[rs].date-=Tree[p].Add;
        Tree[rs].Ori+=Tree[p].Add;
        if(Tree[rs].Ori_lazy!=0)
        {
            Tree[rs].Ori_lazy+=Tree[p].Add;
        }
        else
        {
            Tree[rs].Add+=Tree[p].Add;            
        }
        Tree[p].Add=0;
    }
}
void Build(int p,int l,int r)
{
    Tree[p].l=l;
    Tree[p].r=r;
    Tree[p].Add=0;
    Tree[p].Ori_lazy=0;
    if(l==r)
    {
        Tree[p].date=R[l];
        Tree[p].Ori=a[l];
        return;
    }
    int mid=(l+r)>>1;
    Build(ls,l,mid);
    Build(rs,mid+1,r);
    push_up(p);
}
void Update_add(int p,int l,int r,int x)
{
    if(Tree[p].l>=l&&Tree[p].r<=r)
	{
		Tree[p].Ori += x;
        Tree[p].date-=x;
        if(Tree[p].Ori_lazy!=0)
        {
            Tree[p].Ori_lazy+=x;
        }
        else
        {
            Tree[p].Add+=x;
        }
     	return;
    }
    push_down(p);
    int mid=(Tree[p].l+Tree[p].r)>>1;
    if(l<=mid)
    {
        Update_add(ls,l,r,x);
    }
    if(r>mid)
    {
        Update_add(rs,l,r,x);
    }
    push_up(p);
}
void Update_fill(int p,int l,int r,int x)
{
    if(Tree[p].l>=l&&Tree[p].r<=r)
    {
        Tree[p].Add=0;
        Tree[p].Ori=x;
        Tree[p].Ori_lazy=x;
        Tree[p].date=get(x);
        return;
    }
    push_down(p);
    int mid=(Tree[p].l+Tree[p].r)>>1;
    if(l<=mid)
    {
        Update_fill(ls,l,r,x);
    }
    if(r>mid)
    {
        Update_fill(rs,l,r,x);
    }
    push_up(p);
}

long long Query(int p,int x)
{
    if(Tree[p].l==Tree[p].r)
    {
        return Tree[p].Ori;
    }
    push_down(p);
    int mid=(Tree[p].l+Tree[p].r)>>1;
    if(x<=mid)
    {
        return Query(ls,x);
    }
    else
    {
        return Query(rs,x);
    }
}

void upd(int p) {
	if (Tree[p].date >= 0) {
		return ;
	} else if (Tree[p].l == Tree[p].r) {
		Tree[p].date = get(Tree[p].Ori);
        return ;
	}
	push_down(p);
	upd(p << 1);
	upd(p << 1 | 1);
	push_up(p);
}
signed main()
{
//    freopen("data.in","r",stdin);
//    freopen("data.out","w",stdout);
    B[0]=1;
    for(int i=1;i<=11;i++)
    {
        B[i]=((long long)B[i-1]*42);
    }

    scanf("%lld %lld",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        int Tp=lower_bound(B,B+11+1,a[i])-B;
        R[i]=B[Tp]-a[i];
    }
    int Cnt=0;
    Build(1,1,n);

    while(q--)
    {
        scanf("%lld",&op);
        if(op==1)
        {
            scanf("%lld",&x);
            printf("%lld\n",Query(1,x));
        }
        else if(op==2)
        {
            
            scanf("%lld %lld %lld",&l,&r,&x);
             Update_fill(1,l,r,x);
        }
        else
        {  
            scanf("%lld %lld %lld",&l,&r,&x);
            Update_add(1,l,r,x);
            upd(1);
            while(Tree[1].date==0)
            {
                Update_add(1,l,r,x);
                upd(1);
            }
        }
    }
}

[UR19]前进四

维护单调栈有一个\(log^2(n)\)的做法,这里肯定是不能再优化的

于是这里我们可以换一个角度看待问题

不妨枚举位置维护每个询问

考虑这里的单调栈的过程,我们发现从后往前,只要新添加的数小于当前最小值就会使答案\(+1\)

考虑用线段树维护时间轴,区间取\(min\)即可,似乎势能线段树只取\(min\)的时间复杂度是\(O(log(n))\)的

话说4道题卡了3道题的常

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Og")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#define U 10000
#define N 1000012
#define INF 0x3f3f3f3f
#define MAX_READ 33554432
using namespace std;
inline int max(int x,int y){return (x>y)?x:y;}
char buf[MAX_READ],*l=buf;
inline int read()
{
	int X=0;char ch=0;while('0'>ch||ch>'9')ch=*(l++);
	while('0'<=ch&&ch<='9')X=(X<<3)+(X<<1)+(ch^48),ch=*(l++);return X;
}
char CH[12000012],nu[U][4],fnu[U][4];int cn=0,le[U];
inline void wr(int x){if(x<10000){memcpy(CH+cn,nu[x],le[x]);cn+=le[x];return;}int v=x/10000;wr(v);x-=v*10000;memcpy(CH+cn,fnu[x],4);cn+=4;}
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int MAXN=1e6+5;
int n;
int q;
int x,y;
int op;
int Ne[MAXN];
int Hea[MAXN];
int Val[MAXN];
int A[MAXN];
int Nex[MAXN];
int Head[MAXN];
int Ans[MAXN];

struct Seg{
    int ms;
    int mx;
    int l,r;
    int add;
    int lazy;
}Tree[MAXN*4];
inline void push_up(int p)
{
    if(Tree[ls].mx==Tree[rs].mx)
    {
        Tree[p].mx=Tree[ls].mx;
        Tree[p].ms=max(Tree[ls].ms,Tree[rs].ms);
    }
    else if(Tree[ls].mx>Tree[rs].mx)
    {
        Tree[p].mx=Tree[ls].mx;
        Tree[p].ms=max(Tree[ls].ms,Tree[rs].mx);
    }   
    else
    {
        Tree[p].mx=Tree[rs].mx;
        Tree[p].ms=max(Tree[rs].ms,Tree[ls].mx);
    }
}
inline void push_down(int p)
{
    if(Tree[p].add)
    {
        int Mxc=max(Tree[ls].mx,Tree[rs].mx);
        if(Tree[ls].mx==Mxc)
        {
            Tree[ls].mx=Tree[p].lazy;
            Tree[ls].lazy=Tree[p].lazy;
            Tree[ls].add+=Tree[p].add;
        }
        if(Tree[rs].mx==Mxc)
        {
            Tree[rs].mx=Tree[p].lazy;
            Tree[rs].lazy=Tree[p].lazy;
            Tree[rs].add+=Tree[p].add;
        }
        Tree[p].add=0;
        Tree[p].lazy=0;
    }
}
inline void Build(int p,int l,int r)
{
    Tree[p].l=l;
    Tree[p].r=r;
    Tree[p].add=0;
    Tree[p].mx=0x3f3f3f3f;
    Tree[p].ms=0;
    if(l==r)
    {
        return;
    }
    int mid=(l+r)>>1;
    Build(ls,l,mid);
    Build(rs,mid+1,r);
}
inline void Update(int p,int l,int r,int k)
{
    if(l>r)
    {
        return;
    }
    if(Tree[p].mx<=k)
    {
        return;
    }
    if(Tree[p].l==Tree[p].r)
    {
        if(k<Tree[p].mx)
        {
            Tree[p].mx=k;
            Tree[p].add++;
        }
        return;
    }
    if(Tree[p].l>=l&&Tree[p].r<=r)
    {
        if(Tree[p].mx<=k)
        {
            return;
        }
        else if(k>Tree[p].ms)
        {
            Tree[p].mx=k;
            Tree[p].lazy=k;
            Tree[p].add++;
            return;
        }
    }
    push_down(p);
    int mid=(Tree[p].l+Tree[p].r)>>1;
    if(l<=mid)
    {
        Update(ls,l,r,k);
    }
    if(r>mid)
    {
        Update(rs,l,r,k);
    }
    push_up(p);
}
inline int Query(int p,int x)
{
    if(Tree[p].l==Tree[p].r)
    {
        return Tree[p].add;
    }
    push_down(p);
    int mid=(Tree[p].l+Tree[p].r)>>1;
    if(x<=mid)
    {
        return Query(ls,x);
    }
    else
    {
        return Query(rs,x);
    }
}
inline void PreGet(){int i,x;for(i=0;i<U;i++){for(x=i;x;x/=10)nu[i][le[i]++]=(x%10)^48;memcpy(fnu[i],nu[i],4);for(x=le[i];x<=3;++x)fnu[i][x]=48;reverse(nu[i],nu[i]+le[i]);reverse(fnu[i],fnu[i]+4);}nu[0][0]=48;le[0]=1;}
int main()
{
  PreGet();fread(buf,1,MAX_READ,stdin);
    n=read();
    q=read();
    for(int i=1;i<=n;i++)
    {
        x=read();
        A[i]=x;
        Hea[i]=q+1;
        Ne[q+1]=0;
    }
    for(int i=1;i<=q;i++)
    {
        op=read();
        if(op==1)
        {
            x=read();
            y=read();
            Val[i]=y;
            Ne[i]=Hea[x];
            Hea[x]=i;
        }
        else
        {
            x=read();
            Nex[i]=Head[x];
            Head[x]=i;
        }
    }
    Build(1,1,q);
    
    for(int i=n;i>=1;i--)
    {
        int Lap=q;
        for(int j=Hea[i];j;j=Ne[j])
        {
            int L=j;
            int Rx=Lap;
            if(j!=(q+1))
            {
                Update(1,max(L,1),Rx,Val[j]);
            }
            else
            {
                Update(1,1,Rx,A[i]);
            }
            
            Lap=j-1;
        }
        for(int j=Head[i];j;j=Nex[j])
        {
            Ans[j]=Query(1,j);
        }
    }
    for(int i=1;i<=q;i++)
    {
        if(Ans[i])
        {
            wr(Ans[i]),CH[cn++]='\n';
        }
    }
    fwrite(CH,1,cn,stdout);

}

标签：lazy,rs,int,练习,Tree,long,Ori,数据结构
From： https://www.cnblogs.com/kid-magic/p/17527281.html

相关文章

  • 数据结构（第六章）
    数据结构（第六章）图定义：图是由顶点的有穷非空集合和顶点之间边的集合组成的，通常表示为G（V,E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。特性：​在图中数据元素，我们称之为顶点。任意两个顶点之间都有可能有关系，顶点之间的逻辑关系用边来表示。无向图定义：如......
  • 循环语句-while-练习题
    1'''2练习while循环3其实就是练习手感，不停的敲4'''56'''71.打印星号(三⻆形)8*9**10***11****12*****13找规律，弄懂需求：5行5列，只显示了column<=row。显示的内容是*14解决：2个循环搞定15'''1617row=118whi......
  • wpf小说阅读器 ----wpf练习demo
    1.登录窗口布局<Grid><Grid.ColumnDefinitions><ColumnDefinition/><ColumnDefinitionWidth="2*"/></Grid.ColumnDefinitions><Border><Border.Backgro......
  • 数据结构--单向链表
    如果对于顺序表的结构已经大致了解，那么对单向链表的学习就会轻松一些。顺序存储中的数据因为挤在一起而导致需要成片移动，那很容易想到的解决方案是将数据离散地存储在不同内存块中，然后在用来指针将它们串起来。这种朴素的思路所形成的链式线性表，就是所谓的链表。顺序表和链表在内存......
  • 牛客练习赛 112 B~C题题解
    卡B题了，难受B.qsggandSubarrayB-qsggandSubarray_牛客练习赛112(nowcoder.com)题意给定一个长为n的序列，求有多少个子区间的按位与和为0。思路要想按位与之和为0，那么对于区间的所有数，每个二进制位都要有一个0。设f[i]表示二进制位i的最右边一个0出现的位置，枚举序列的每......
  • js简单小练习
    1计算二个数字的和并输出结果functionadd(a,b){console.log(a+b)}add(2,3)2判断一个数字是否为偶数，并在控制台打印相应结果functionisEven(a){if(a%2==0)returnconsole.log('even')console.log('odd')}isEven(2)3找出一个数组中的最大值并打印出来constarray=[1......
  • 刻意练习：从新手到专家
    前几年看过一本书：《刻意练习，如何从新手到大师》，里面提到的关于学习和成长的方法，让我很是受用。最近看完了另一本关于学习技能和个人认知成长的书，其中也提到了刻意练习的方法。很多同学咨询我，如何提升自己的专业技术能力，我其实很推荐大家看看《刻意练习》这本书，按照文中提到的方......
  • 数据结构与算法coding过程中的记录
     1.init()时一定要记得malloc()申请新的内存空间（如果不申请内存空间程序返回的值是有内存里的脏数据，把人看得云里雾里找不到问题出在哪）2.带头结点单链表尾插法要注意：若LNode*p=L->next；循环条件是while(p!=NULL){p=p->next;}，那么最后的p是NULL，此时在p(NULL)后插一个结点......
  • 《数据结构与算法》之图
    导言：图是数据结构教材上的最后一种数据结构了，它的使用范围最广，最多，也是最贴合我们实际生活的，图是一个多对多的数据结构，在前面的学习，了解到了一对一的数据结构----线性结构，以及一对多的结构----树形结构，现在要学的多对多的结构----图，图是对我们现实生活中很多实体的抽象，因为实际......
  • 图论练习
    图论练习学长的题果然恐怖如斯CF1458DFlipandReverse这个操作看着很奇怪\(0\)先看成\(-1\)那可操作的区间就是和为\(0\)对每一个前缀和的值建点,把每种元素看作边那可操作的区间就是一个环然后你会发现一个操作就是相当于是反着走这个环这里我们考虑连成无向边考虑连......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99