35pts 求调
查看原帖
35pts 求调
504093
dyc2022楼主2024/10/22 22:52

rt,开了三棵线段树,只对了 #1~5,7,8。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 300006
#define WIN puts("cont")
#define LOSE puts("tetris")
using namespace std;
int n,m,c1,c2,w1,w2;
int a[N],s[N];
int tree1[N<<2],tree2[N<<2],sum[N<<2],tag[N<<2],findans;
/*
s for the sum of [1, i]
tree1 for maxinum of the sum of [i, i+c2-1]
tag is the lazy-tag of tree1
tree2 for maxinum of a_i
sum for the sum of a_i

build() is for building the segment trees
update_range() is for updating tree1
update_single() is for updating tree2 & sum
query_max() is for querying tree2
query_whole_(min/max)() is for querying a whole node on segment trees
query_range_(min/max)() is for binary searching on segment trees
query_sum() is for querying sum

Very good, but the code is like sh*t.
*/
void build(int p,int l,int r)
{
    if(l==r)
    {
        tree1[p]=s[min(l+c2-1,n)]-s[l-1];
        sum[p]=tree2[p]=a[l];
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    tree1[p]=max(tree1[p<<1],tree1[p<<1|1]);
    tree2[p]=max(tree2[p<<1],tree2[p<<1|1]);
    sum[p]=sum[p<<1]+sum[p<<1|1];
}
void addtag(int p,int x){tag[p]+=x,tree1[p]+=x;}
void push_down(int p)
{
    if(tag[p])
    {
        addtag(p<<1,tag[p]);
        addtag(p<<1|1,tag[p]);
        tag[p]=0;
    }
}
void update_range(int p,int l,int r,int L,int R,int x)
{
    if(L<=l&&r<=R){addtag(p,x);return;}
    push_down(p);
    int mid=l+r>>1;
    if(L<=mid)update_range(p<<1,l,mid,L,R,x);
    if(R>mid)update_range(p<<1|1,mid+1,r,L,R,x);
    tree1[p]=max(tree1[p<<1],tree1[p<<1|1]);
}
void update_single(int p,int l,int r,int k,int x)
{
    if(l==r){tree2[p]+=x,sum[p]+=x;return;}
    push_down(p);
    int mid=l+r>>1;
    if(k<=mid)update_single(p<<1,l,mid,k,x);
    else update_single(p<<1|1,mid+1,r,k,x);
    tree2[p]=max(tree2[p<<1],tree2[p<<1|1]);
    sum[p]=sum[p<<1]+sum[p<<1|1];
}
int query_max(int p,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)return tree2[p];
    push_down(p);
    int mid=l+r>>1,ret=-1;
    if(L<=mid)ret=max(ret,query_max(p<<1,l,mid,L,R));
    if(R>mid)ret=max(ret,query_max(p<<1|1,mid+1,r,L,R));
    return ret;
}
int query_sum(int p,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)return sum[p];
    push_down(p);
    int mid=l+r>>1,ret=0;
    if(L<=mid)ret+=query_sum(p<<1,l,mid,L,R);
    if(R>mid)ret+=query_sum(p<<1|1,mid+1,r,L,R);
    return ret;
}
int query_whole_min(int p,int l,int r)
{
    if(l==r)return l;
    push_down(p);
    int mid=l+r>>1;
    if(tree1[p<<1]>w2)return query_whole_min(p<<1,l,mid);
    return query_whole_min(p<<1|1,mid+1,r);
}
int query_whole_max(int p,int l,int r)
{
    if(l==r)return l;
    push_down(p);
    int mid=l+r>>1;
    if(tree1[p<<1|1]>w2)return query_whole_max(p<<1|1,mid+1,r);
    return query_whole_max(p<<1,l,mid);
}
int query_range_min(int p,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)
    {
        if(tree1[p]>w2&&findans)
        {
            findans=0;
            return query_whole_min(p,l,r);
        }
        return 1e15;
    }
    push_down(p);
    int mid=l+r>>1,ret=1e15;
    if(L<=mid)ret=min(ret,query_range_min(p<<1,l,mid,L,R));
    if(R>mid)ret=min(ret,query_range_min(p<<1|1,mid+1,r,L,R));
    return ret;
}
int query_range_max(int p,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)
    {
        if(tree1[p]>w2&&findans)
        {
            findans=0;
            return query_whole_max(p,l,r);
        }
        return -1e15;
    }
    push_down(p);
    int mid=l+r>>1,ret=-1e15;
    if(L<=mid)ret=max(ret,query_range_max(p<<1,l,mid,L,R));
    if(R>mid)ret=max(ret,query_range_max(p<<1|1,mid+1,r,L,R));
    return ret;
}
main()
{
    scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&c1,&c2,&w1,&w2);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];
    build(1,1,n);
    while(m--)
    {
        int opt,l,r,x,y;
        scanf("%lld",&opt);
        if(opt==1)
        {
            scanf("%lld%lld",&x,&y);
            update_single(1,1,n,x,y);
            update_range(1,1,n,max(1ll,x-c2+1),x,y);
        }
        else
        {
            scanf("%lld%lld",&l,&r);
            int len=r-l+1;
            if(len<c2)
            {
                if(query_sum(1,1,n,l,r)<=w1&&len<=c1)WIN;
                else if(query_sum(1,1,n,l,r)>w2)LOSE;
                else if(query_max(1,1,n,l,r)<=w1)WIN;
                else LOSE;
            }
            else
            {
                int i=query_range_min(findans=1,1,n,l,r);
                int j=query_range_max(findans=1,1,n,l,r)+c2-1;
                if(i>n)
                {
                    if(query_max(1,1,n,l,r)<=w1)WIN;
                    else LOSE;
                }
                else if(len<=c1&&query_max(1,1,n,l,r)<=w1)WIN;
                else LOSE;
            }
        }
    }
    return 0;
}
2024/10/22 22:52
加载中...