BZOJ 3878 Ahoi2014 奇怪的計算器 線段樹

BZOJ 3878 Ahoi2014 奇怪的計算器 線段樹

題目大意：給定n個操作，每個操作有四種形式，操作之後若R就變成R，現在給定q個輸入，求他們的輸出

n,q<=10W

將這q個數建立線段樹，四個操作都可以在線段樹上完成

但是溢出怎麼辦呢？

容易發現若x<=y，那麼操作過後x一定<=y

因為四個操作都是線性的，溢出也不會反轉兩個數的大小關系

那麼我們可以預先將q個數排序 那麼溢出的數一定是連續的兩段 區間修改就行了

至於怎麼找兩端溢出的區間…… 每個節點維護一個區間最大值和最小值就好了

此外數據還是比較良心的 不會出現爆long long這種P事 放心寫吧

這麼簡單的思路我他媽的居然寫了整整四遍的代碼- - 下次寫代碼之前一定要想清楚- - 至少TM先手模擬過樣例啊QAQ

#include 
#include 
#include 
#include 
#include 
#define M 100100
using namespace std;
int n,m,L,R;
int q[M];
long long a[M];
struct Operation{
	int type,x;
	friend istream& operator >> (istream &_,Operation &o)
	{
		char p[10];
		scanf("%s%d",p,&o.x);
		switch(p[0])
		{
			case '+':o.type=1;break;
			case '-':o.type=2;break;
			case '*':o.type=3;break;
			case '@':o.type=4;break;
		}
		return _;
	}
}operations[M];
struct Segtree{
	Segtree *ls,*rs;
	long long times_mark,k,b;
	long long min_num,max_num;
	Segtree():ls(0x0),rs(0x0),times_mark(1),k(0),b(0) {}
	void Build_Tree(int x,int y)
	{
		int mid=x+y>>1;
		min_num=a[x];
		max_num=a[y];
		if(x==y) return ;
		(ls=new Segtree)->Build_Tree(x,mid);
		(rs=new Segtree)->Build_Tree(mid+1,y);
	}
	void Get_Mark(int x,int y,long long _,long long __,long long ___)
	{
		min_num=_*min_num+__*a[x]+___;
		max_num=_*max_num+__*a[y]+___;

		times_mark*=_;k*=_;b*=_;
		k+=__;
		b+=___;
	}
	void Push_Down(int x,int y)
	{
		int mid=x+y>>1;
		ls->Get_Mark(x,mid,times_mark,k,b);
		rs->Get_Mark(mid+1,y,times_mark,k,b);
		times_mark=1;k=b=0;
	}
	int Get_Ans(int x,int y,int pos)
	{
		int mid=x+y>>1;
		if(x==y) return max_num;
		Push_Down(x,y);
		if(pos<=mid)
			return ls->Get_Ans(x,mid,pos);
		else
			return rs->Get_Ans(mid+1,y,pos);
	}
	void Get_L(int x,int y)
	{
		int mid=x+y>>1;
		if(x==y)
		{
			Get_Mark(x,y,0,0,L);
			return ;
		}
		Push_Down(x,y);
		if(rs->min_numGet_Mark(x,mid,0,0,L),rs->Get_L(mid+1,y);
		else
			ls->Get_L(x,mid);
		min_num=ls->min_num;
		max_num=rs->max_num;
	}
	void Get_R(int x,int y)
	{
		int mid=x+y>>1;
		if(x==y)
		{
			Get_Mark(x,y,0,0,R);
			return ;
		}
		Push_Down(x,y);
		if(ls->max_num>R)
			rs->Get_Mark(mid+1,y,0,0,R),ls->Get_R(x,mid);
		else
			rs->Get_R(mid+1,y);
		min_num=ls->min_num;
		max_num=rs->max_num;
	}
}*tree=new Segtree;
int main()
{

	int i;
	cin>>n>>L>>R;
	for(i=1;i<=n;i++)
		cin>>operations[i];
	cin>>m;
	for(i=1;i<=m;i++)
		scanf("%d",&q[i]),a[i]=q[i];
	sort(a+1,a+m+1);
	tree->Build_Tree(1,m);
	for(i=1;i<=n;i++)
	{
		switch(operations[i].type)
		{
			case 1:tree->Get_Mark(1,m,1,0,operations[i].x);break;
			case 2:tree->Get_Mark(1,m,1,0,-operations[i].x);break;
			case 3:tree->Get_Mark(1,m,operations[i].x,0,0);break;
			case 4:tree->Get_Mark(1,m,1,operations[i].x,0);break;
		}
		if(tree->min_numGet_L(1,m);
		if(tree->max_num>R)
			tree->Get_R(1,m);
	}
	for(i=1;i<=m;i++)
	{
		int pos=lower_bound(a+1,a+m+1,q[i])-a;
		printf("%d\n",tree->Get_Ans(1,m,pos) );
	}
	return 0;
}