算法竞赛2021 ICPC Southeastern Europe Regional Contest_New Queries
#include "stdafx.h"
#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=250000,maxt=maxn<<2,maxq=20000;
int n,m,Q,a[4][maxn+5]={
{0,1,2, 3, 4, 5},
{0,10, 8, 6, 4, 2}
};
int ans[maxq+5];
int tp[maxq+5],ID[maxq+5],X[maxq+5],lq[maxq+5],rq[maxq+5],w[maxq+5];
int flag[maxt+5][4],tag[maxt+5][4],MIN[maxt+5][16];
vector<int> e[maxq+5],q[maxq+5];
int top;
vector< pair<int*,int> > stk;
void Build(int L,int R,int p=1){
for (int i=0;i<n;i++) flag[p][i]=1e9;// as a flag
if (L==R){
for (int i=1;i<(1<<n);i++)
for (int j=0;j<n;j++)
{
if (i&1<<j) MIN[p][i]+=a[j][L];
// printf("\n L==R Build %d %d, %d " ,1<<j,j, a[j][L]); printf(" , M= %d\n" ,MIN[p][1<<j]);
}
return;
}
int mid=(R+L)>>1;
Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);
printf("\n");
for (int i=1;i<(1<<n);i++)
MIN[p][i]=min(MIN[p<<1][i],MIN[p<<1|1][i]),printf(" p=%d , i= %d, M =%d " ,p,i,MIN[p][i]);
}
void Change(int *x,int y) {
printf("\nChange %d, %d\n",*x,y);
top++;stk.push_back(mp(x,*x));
*x=y;
}
void Pop(int lst) {
while (top!=lst) top--,*stk[top].fr=stk[top].sc,stk.pop_back();
}
void Pushup(int p) {
for (int i=1;i<(1<<n);i++) Change(&MIN[p][i],min(MIN[p<<1][i],MIN[p<<1|1][i]));
}
void Addtag(int line,int p,int k) // increase
{
for (int i=1<<line;i<(1<<n);i=(i+1)|(1<<line)) Change(&MIN[p][i],MIN[p][i]+k);
Change(&tag[p][line],tag[p][line]+k);
}
void Setval(int line,int p,int k)// set value
{
for (int i=1<<line;i<(1<<n);i=(i+1)|(1<<line)) Change(&MIN[p][i],MIN[p][i^(1<<line)]+k);
if(tag[p][line])Change(&tag[p][line],0);
Change(&flag[p][line],k);
}
void Pushdown(int p){
for (int i=0;i<n;i++)
{
if (flag[p][i]<1e9) Setval(i,p<<1,flag[p][i]),Setval(i,p<<1|1,flag[p][i]),Change(&flag[p][i],1e9);// set value
if (tag[p][i]) Addtag(i,p<<1,tag[p][i]),Addtag(i,p<<1|1,tag[p][i]),Change(&tag[p][i],0);// increase
}
}
void Increase(int line,int L,int R,int k,int l=1,int r=m,int p=1){
if (L==l && r==R) return Addtag(line,p,k);
int mid=(r+l)>>1;
Pushdown(p);
if (R<=mid) Increase(line,L,R,k,l,mid,p<<1); else if (L>mid) Increase(line,L,R,k,mid+1,r,p<<1|1);
else Increase(line,L,mid,k,l,mid,p<<1),Increase(line,mid+1,R,k,mid+1,r,p<<1|1);
Pushup(p);
}
void Cover(int line,int L,int R,int k,int l=1,int r=m,int p=1){
if (L==l && r==R) return Setval(line,p,k);
int mid=(r+l)>>1;
Pushdown(p);
if (R<=mid) Cover(line,L,R,k,l,mid,p<<1); else if (L>mid) Cover(line,L,R,k,mid+1,r,p<<1|1);
else Cover(line,L,mid,k,l,mid,p<<1),Cover(line,mid+1,R,k,mid+1,r,p<<1|1);
Pushup(p);
}
int Ask(int L,int R,int l=1,int r=m,int p=1){
if (L==l && r==R) return MIN[p][(1<<n)-1];
Pushdown(p);
int mid=(r+l)>>1;
if (R<=mid) return Ask(L,R,l,mid,p<<1);
else if (L>mid) return Ask(L,R,mid+1,r,p<<1|1);
else return min(Ask(L,mid,l,mid,p<<1),Ask(mid+1,R,mid+1,r,p<<1|1));
}
void Solve(int x){
for (auto i:q[x]){
printf("\n x: %d %d, %d\n",x, top,i);
ans[i]=Ask(lq[i],rq[i]);
}
int top0=top;
for (auto u:e[x]){
printf("x1: %d %d, %d\n",x, top,u);
if (tp[u]==1) Increase(X[u],lq[u],rq[u],w[u]);
else Cover(X[u],lq[u],rq[u],w[u]);
printf("x2: %d %d\n",x, top);
//for (int i=0;i<top;i++)printf("x2: i=%d %d\n",i, stk[i].sc);
Solve(u);Pop(top0);
printf("x3: %d %d\n",x, top);
}
}
int main(){
n=2;m=5;Q=8;
Build(1,m);
int QA[][6]={
{3, 0, 2, 5},
{2, 0, 2, 1, 5, 0},
{3, 2, 2, 5},
{1, 0, 1, 3, 5 ,5},
{3, 4, 2, 5},
{1, 2, 2, 1, 3, 2},
{3, 2, 2, 5},
{3, 6, 2, 5}};
for (int i=1;i<=Q;i++){
tp[i]=QA[i-1][0];ID[i]=QA[i-1][1];
if (tp[i]<=2)
{
X[i]=QA[i-1][2]-1;
lq[i]=QA[i-1][3];rq[i]=QA[i-1][4];w[i]=QA[i-1][5];
e[ID[i]].push_back(i);
} //readi(X[i]),X[i]--,readi(lq[i]),readi(rq[i]),readi(w[i]),e[ID[i]].push_back(i);
else //readi(lq[i]),readi(rq[i]),q[ID[i]].push_back(i);
{
lq[i]=QA[i-1][2];rq[i]=QA[i-1][3];q[ID[i]].push_back(i);
}
}
Solve(0);
for (int i=1;i<=Q;i++) if (tp[i]==3) printf("%d\n",ans[i]);
// for (int i=1<<1;i<(1<<3);i=(i+1)|(1<<1)) printf("\n 1<< %d ",i);
return 0;
}
