Codeforces Round #569(Div.2)(D/구성+E/세그먼트 트리)

사고의 근원
https://codeforces.com/blog/entry/67891(공식 문제풀이)
사실 가끔은 공식 문제풀이를 죽어라 하는 게 나쁠 게 없어요.
D.Tolik and His Uncle
제목.
n*m(1<=n*m<=1e6)의 격자도가 있는데, 초기 소인은 (1,1)에 위치하고,
다음 점프는 임의의 아직 점프하지 않은 위치로 점프할 수 있다. 예를 들어 (x, y)로 점프하면 차향량은 (x-1, y-1)이고,
모든 점프의 차향량 (dx,dy) 에 따라 모든 위치에 접근하여 다음 점프의 서열을 출력해야 한다
문제풀이
마지막으로 벡터가 다른 요구는 자신이 그림을 그릴 때 두 개의 화살표가 평행이고 길이가 같다는 것이다
1차원 1*m의 상황을 고려하면 (1,1)에서 (1,m)로 뛰기(1,2)에서 (1,m-1)로 뛰는 것과 같은 것들은 매번 길이가 1씩 줄어들기 때문에 최종적으로 다르다.
그 두 줄도 유사하다. (1,1)에서 (2,m)로 뛰기(1,2)에서 (2,m-1)로 뛰고 이 과정을 반복한다.
n줄의 경우 (1,1)에서 (n,m)로 뛰기(1,2)에서 (n,m-1)로 뛰고, 대칭성 때문에 최종적으로 (n,1)에 떨어진다.
다시 (2,1)로 뛰면 자문제 n-2 줄이 된다.
특히 n이 홀수라면 가운데 줄은 일차 점프법을 채택하면 된다
소감
구조문제는 항상 지능이 짓눌리는 느낌이 든다.
코드

#include 
using namespace std;
int n,m,mid;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n/2;++i)
	{
		for(int j=1;j<=m;++j)
		{
			printf("%d %d
",i,j);
			printf("%d %d
",n+1-i,m+1-j);
		}
	}
	if(n&1)
	{
		mid=n-n/2;//      
		for(int j=1;j<=m/2;++j)
		{
			printf("%d %d
",mid,j);
			printf("%d %d
",mid,m+1-j);
		}
		if(m&1)printf("%d %d
",mid,m-m/2);
	}
	return 0;
}

 
E.Serge and Dining Room
제목.
n(n<=3e5)개 요리 가격, i개 요리 가치ai(1<=ai<=1e6)
m(m<=3e5)개 초등학생, 제j개인은 bj위안(1<=bj<=1e6)
매번 초등학생은 자신이 고를 수 있는 가장 비싼 요리를 골라서 골라서 Serge에게 고르게 하고,
그러나 q(q<=3e5)개의 수정이 있고, 첫 번째 수정은op[k],pos[k],x[k],op[k]={1,2}를 포함한다.
① 1px는 a[p]의 값을 x로 바꾸는 것을 의미한다
② 2px는 b[p]의 값을 x로 바꾸는 것을 의미한다
수정이 끝난 후 Serge는 무한한 돈이 있어 초등학생이 뽑지 않은 가장 비싼 것을 고르고,
그에게 고른 요리의 값을 물어보고, 고른 요리가 없으면 출력-1
문제풀이
이 답을 점차적으로 고려하는 가격 x,
반드시 어느 순간에 가격x보다 큰 요리 수가 x보다 큰 초등학생 돈의 개수보다 많은 상황이 나타날 것이다. 이 조건을 만족시키는 가장 큰 x가 바로 답이다.
 
그리고 앞의 x가 모두 이 조건을 만족시키지 못하기 때문에 초등학생 수가 가진 돈은 시종일관 채소를 살 수 있다.
체감 순서에서 첫 번째로 나타난 초등학생의 돈으로 첫 번째로 나온 음식을 욕심내고, 두 번째는 두 번째를 사는 것으로 유추하면 증명할 수 있다.
 
읽은 모든 요리 가격, 초등학생 돈, 수정된 값을 이산화하고 3*3e5의 값을 유지하는 라인 트리
각 점 유지 보수는 이 점이 대표하는 값의 개수, 즉 접미사 합보다 크고,
pushup에서 좌우자의 최대치, 최대치>0은 최소한 한 자가 조건을 만족시켜야 한다는 것을 설명한다
수정 시, 단점 수정 을 앞 의 수 의 접미사 와 구간 수정 으로 바꾸다
조회할 때, 먼저 나무 전체에 답이 있는지 없는지를 판별하고, 어떤 것은 오른쪽을 우선하고, 그 다음에 왼쪽을 판별한다.
소감
cf393의 E라인 트리를 만들었고 단점 접미사와 단점을 수정하여 접미사 변경과 마지막으로 가장 오른쪽에 0보다 큰 위치를 물었습니다.
코드가 똑같다고 할 수 있는데 그 문제처럼 생각을 돌리는 게 힘들어...
그렇지 않으면 경기에서 2400의 E를 만들 수 있다면 바로 보라색이라고 할 수 있다.
코드

#include
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r 
using namespace std;
const int N=3e5+10;
const int V=3*N;//        
int n,m,q;
int a[N],b[N],op[N],pos[N],x[N];
int c[V],cnt;//            a[]b[]x[]    
int suf[4*V],cov[4*V];//               pos    [1,pos]         
//pushup                            max>0       >0  
void pushdown(int p,int l,int r)
{
	if(!cov[p])return;
	suf[p<<1]+=cov[p];
	cov[p<<1]+=cov[p];
	suf[p<<1|1]+=cov[p];
	cov[p<<1|1]+=cov[p];
	cov[p]=0;
}
void update(int p,int l,int r,int ql,int qr,int v)
{
	if(ql<=l&&r<=qr)
	{
		suf[p]+=v;
		cov[p]+=v;
		return; 
	} 
	int mid=l+r>>1;
	pushdown(p,l,r);
	if(ql<=mid)update(lson,ql,qr,v);
	if(qr>mid)update(rson,ql,qr,v);
	suf[p]=max(suf[p<<1],suf[p<<1|1]);
}
int ask(int p,int l,int r)
{
	if(l==r)return l;// c           pos c[pos]       
	int mid=l+r>>1;
	pushdown(p,l,r);
	if(suf[p<<1|1]>0)return ask(rson);
	else return ask(lson);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		c[++cnt]=a[i];
	}
	for(int i=1;i<=m;++i)
	{
		scanf("%d",&b[i]);
		c[++cnt]=b[i];
	}
	scanf("%d",&q);
	for(int i=1;i<=q;++i)
	{
		scanf("%d%d%d",&op[i],&pos[i],&x[i]);
		c[++cnt]=x[i];
	}
	sort(c+1,c+cnt+1);
	cnt=unique(c+1,c+cnt+1)-(c+1);
	for(int i=1;i<=n;++i)
	{
		a[i]=lower_bound(c+1,c+cnt+1,a[i])-c;
		update(1,1,cnt,1,a[i],1);
	}
	for(int i=1;i<=m;++i)
	{
		b[i]=lower_bound(c+1,c+cnt+1,b[i])-c;
		update(1,1,cnt,1,b[i],-1);
	}
	for(int i=1;i<=q;++i)
	x[i]=lower_bound(c+1,c+cnt+1,x[i])-c;
	//a[] +1 b[] -1           >0             
	for(int i=1;i<=q;++i)
	{
		if(op[i]==1)
		{
			update(1,1,cnt,1,a[pos[i]],-1);//    
			a[pos[i]]=x[i];
			update(1,1,cnt,1,a[pos[i]],1);//    
		}
		else if(op[i]==2)
		{
			update(1,1,cnt,1,b[pos[i]],1);//    
			b[pos[i]]=x[i];
			update(1,1,cnt,1,b[pos[i]],-1);//    
		}
		if(suf[1]<=0)puts("-1");
		else printf("%d
",c[ask(1,1,cnt)]);
	} 
	return 0;
}