2018.10.30 练习赛 T3 [Stark与Riga的卡牌游戏]-[zkw线段树嵌套map]

T3 Stark与Riga的卡牌游戏

题面:

题解:

注意到所有的询问都是以攻击力为询问的下标,考虑以攻击力为区间建立线段树;

显然,对于前三个操作,我们都可以将其转化为对线段树上元素的修改;

我们在每个叶子结点放上另一种数据结构,这种数据结构需要帮助我们快速取出最大最小的元素,这个实现的方法有很多,如:

用优先队列建立一个大根堆一个小根堆,分别对应两个垃圾堆用于将其变为可删除堆;

或者用\(set\)维护以\(A\)为下标的\(H\)有序,可快速取出\(*it,it=s.begin()/(--s.end())\),本文使用\(Map\)作为记录权值\(A\)中的元素个数;

对于区间最小最大的询问,我们将它用线段树动态维护,每次修改更新即可;

区间修改在外层线段树打上区间永久化标记,每次取出加上\(lazy\)值,加入新元素减去\(lazy\)值,删除指定元素减去\(lazy\)值;

这个实现的思路就和\(NOIP2016\)蚯蚓一样了\(qwq\)

\(zkw\)线段树优化常数,当然不写也是可以的;

\(code:\)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define reint register int
#define ll long long
#define ld double
#define l(x) (x<<1)
#define r(x) (x<<1|1)
#define rell register ll
#define mod 7528443412579576937ul
using namespace std;

char buf[1<<20],*p1,*p2;
inline char gc()
{
//    return getchar();
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}

template
inline void read(T &x)
{
    char tt;
    bool flag=0;
    while(!isdigit(tt=gc())&&tt!='-');
    tt=='-'?(flag=1,x=0):(x=tt-'0');
    while(isdigit(tt=gc())) x=(x<<1)+(x<<3)+(tt^'0');
    if(flag) x=-x;
}
const int maxn=1e5+2;

int n,m;
int M=1;
int lazy[maxn<<2];
int mx[maxn<<2],mi[maxn<<2];
mapa[maxn<<2];
mapb;

void pushdown(int x){
	mi[x]=min(mi[l(x)]+lazy[l(x)],mi[r(x)]+lazy[r(x)]);
	mx[x]=max(mx[l(x)]+lazy[l(x)],mx[r(x)]+lazy[r(x)]);
//	printf("%d\n",mx[x]);
}

void update(int x){x+=M;while(x>>=1) pushdown(x);}

void modify(int x,int y,int d)
{
	for(x+=M-1,y+=M+1;x^y^1;x>>=1,y>>=1)
	{
		if(x>=1) pushdown(x);
}

void modify(int x,int y)
{
	int flag=0;
	a[x][y]++;b[x]++;
 	if(mi[x+M]>y) mi[x+M]=y,flag=1;
	if(mx[x+M]>=1;
	}while(x!=1);
	return sum;
}

int getmin(int p,int l,int r,int x,int y)
{
	if(x<=l&&y>=r) return mi[p]+lazy[p];
	int mid=l+r>>1;
	int ans=1e9;
	if(x<=mid) ans=min(ans,getmin(l(p),l,mid,x,y));
	if(y>mid)  ans=min(ans,getmin(r(p),mid+1,r,x,y));
	return ans+lazy[p];
}

int getmax(int p,int l,int r,int x,int y)
{
	if(x<=l&&y>=r) return mx[p]+lazy[p];
	int mid=l+r>>1;
	int ans=-1e9;
	if(x<=mid) ans=max(ans,getmax(l(p),l,mid,x,y));
	if(y>mid)  ans=max(ans,getmax(r(p),mid+1,r,x,y));
	return ans+lazy[p];
}

void del(int x,int y)
{
	bool flag=0;
	b[x]--;if(b[x]==0) b.erase(x);a[x][y]--;
	if(a[x][y]==0)
	{
		a[x].erase(y);
		if(mi[x+M]==y)
		{
			if(a[x].size()==0) mi[x+M]=1e9;
			else mi[x+M]=a[x].begin()->first;
			flag=1;
		}
		if(mx[x+M]==y)
		{
			if(a[x].size()==0) mx[x+M]=-1e9;
			else mx[x+M]=(--a[x].end())->first;
			flag=1;
		} 
		if(flag) update(x);
	}
}

int main()
{
//	freopen("23.txt","w",stdout);
	while(M<=maxn)M<<=1;
	read(n),read(m);
	for(int i=M;i=1;i--) pushdown(i);
	while(m--)
	{
		int opt1,opt2;
		int x,y,z;
		read(opt1),read(opt2);
		read(x),read(y);
		if(opt1==1&&opt2==1) read(z);
		
		if(opt1==0)
		{
			if(opt2==1)
			{
				auto it1=b.lower_bound(y);
				auto it2=--a[it1->first].end();
				int tx=it1->first,ty=it2->first;
				int tmp=getlazy(tx);
				del(tx,ty);ty-=x;
				if(ty+tmp>0) modify(tx,ty); 
			}
			if(opt2==2)
			{
				auto it1=b.lower_bound(y);
				auto it2=a[it1->first].begin();
				int tx=it1->first,ty=it2->first;
				del(tx,ty);
			}
			if(opt2==3)
			{
//				if(x==5&&y==9) printf("**%d\n",y-getlazy(x));
				del(x,y-getlazy(x));
			}
		}
		if(opt1==1)
		{
			if(opt2==1) modify(x,y,z);
			if(opt2==2) printf("%d\n",getmax(1,0,M-1,x,y)+getmin(1,0,M-1,x,y));
			if(opt2==3) modify(x,y-getlazy(x));
		}
//		printf("233_____________:%d\n",getlazy(7));
	}
}
比赛数据结构线段树zkw线段树练习赛题解

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

数据结构--栈（C语言实现）

Ubuntu 断网问题解决

牛客练习赛91（并查集+二维偏序+二分）

[SQL] SQL Server 2019 中LocalDB 报错的问题解决

题解 Count on a tree II/【模板】树分块

HttpURLConnection发送中文乱码问题解决

数据结构----单链表升级版

数据结构/PTA-畅通工程之最低成本建设问题-畅通工程之局部最小花费问题/图/最小生成树

数据结构+java中常用的集合类

1675: [Usaco2005 Feb]Rigging the Bovine Election 竞选划区（题解第一弹）

数据结构 之二叉树

标签