珂朵莉树+线段树#5 TLE求助,如何优化
查看原帖
珂朵莉树+线段树#5 TLE求助,如何优化
516468
_Give_up_楼主2023/2/24 18:55
#include<bits/stdc++.h>
#define IT set<ODT>::iterator
#define int long long
#define N 1000010

using namespace std;

inline int read()
{
    int x = 0,f = 1;
    char c = getchar();
    while(c<'0' || c>'9')
	{
        if(c=='-') f = -1;
        c = getchar();
    }
    while(c>='0' && c<='9')
	{
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    }
    return x*f;
}

void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}

struct ODT
{
	int l,r;
	mutable int v;
	ODT(int L,int R=-1,int V=0): l(L),r(R),v(V) {}
	bool operator <(const ODT &o) const
	{
		return l<o.l;
	}
};

set <ODT> s;
int n,q,t[4*N],b[4*N];

void pushdown(int p,int l,int r)
{
	int mid = (l+r)>>1;
	b[p<<1] += b[p];
	t[p<<1] += b[p]*(mid-l+1);
	b[p<<1|1] += b[p];
	t[p<<1|1] += b[p]*(r-mid);
	b[p] = 0;
}

void pushup(int p)
{
	t[p] = t[p<<1]+t[p<<1|1];
}

void build(int l,int r,int p)
{
	b[p] = 0;
	if (l==r)
	{
		t[p] = 0;
		return ;
	}
	int mid = (l+r)>>1;
	build(l,mid,p<<1);
	build(mid+1,r,p<<1|1);
	pushup(p);
}

void update(int l,int r,int p,int start,int end,int k)
{
	if (start<=l && r<=end)
	{
		b[p] += k;
		t[p] += k*(r-l+1);
		return ;
	}
	int mid = (l+r)>>1;
	pushdown(p,l,r);
	if (start<=mid) update(l,mid,p<<1,start,end,k);
	if (end>mid) update(mid+1,r,p<<1|1,start,end,k);
	pushup(p);
}

int query(int l,int r,int p,int s)
{
	if (l==s && r==s) return t[p];
	pushdown(p,l,r);
	int mid = (l+r)>>1;
	if (s<=mid) return query(l,mid,p<<1,s);
	else return query(mid+1,r,p<<1|1,s);
}

IT split(int x)
{
	IT it = s.lower_bound(ODT(x));
	if (it!=s.end() && it->l==x) return it;
	it--;
	int L = it->l,R = it->r,V = it->v;
	s.erase(it);
	s.insert(ODT(L,x-1,V));
	return s.insert(ODT(x,R,V)).first;
}

void assign(int l,int r,int v)
{
	IT itr = split(r+1),itl = split(l);
	s.erase(itl,itr);
	s.insert(ODT(l,r,v));
}

void add(int c,int v)
{
	IT itr = split(n+1),itl = split(1);
	for (IT it=itl;it!=itr;it++)
		if (it->v==c) update(1,n,1,it->l,it->r,v);
}

signed main()
{
	n=read(),q=read();
	s.insert(ODT(1,n,1));
	while(q--)
	{
		string opt;
		cin >> opt;
		if (opt=="Color")
		{
			int l=read(),r=read(),c=read();
			assign(l,r,c);
		}
		else if (opt=="Add")
		{
			int c=read(),x=read();
			add(c,x);
		}
		else
		{
			int x=read();
			write(query(1,n,1,x));
			printf("\n");
		}
	}
	return 0;
}
2023/2/24 18:55
加载中...