有n个剑客（编号1~n）相约华山比剑，分 m 次决斗，为了节省时间，每次决斗 编号在[l,r]的剑客一起决斗，然后xi获胜。当进行下一次决斗，失败后的剑客可能再参与到决斗，m 次决斗后可能不止一位获胜者（没有失败过就视为获胜者）。
输入 多组测试数据。 对于每组测试数据，第一行输入n和m。接下来输入m行，每行输入l，r，xi。 2 ≤ n ≤ 3*10^5; 1 ≤ m ≤ 3*10^5，l ≤ xi ≤ r 输出 每组测试数据输出n个数字，数字间用空格隔开。第i个数子表示第一次击败i号剑客的剑客编号，若i号剑客是最后的获胜者，输出0； 样例输入 3 2 1 2 2 1 3 2 样例输出2 0 2
tips:区间内的部分点的更新；
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; const int maxn=333333; int n,m; int win[maxn<<2]; int ans[maxn]; void pushup(int rt) { if(win[rt<<1]==win[rt<<1|1]) { win[rt]=win[rt<<1]; } } void update(int x,int y,int z,int rt,int l,int r) { if(win[rt])return;//如果第一次已经被标记了，便不再进行标记 if(l==r) { if(z!=l&&(l>=x&&l<=y)){//加上右边条件的原因：试想 [l,r]=>[1,2],而[x,y]=>[2,3]，进入左子树时是[1,1],[2,3].此时不更新 win[rt]=z; ans[l]=z; } return; } int m=(l+r)>>1; if(x<=m)update(x,y,z,rt<<1,l,m); if(y>m)update(x,y,z,rt<<1|1,m+1,r); pushup(rt); } int main() { while(~scanf("%d %d",&n,&m)) { memset(win,0,sizeof(win)); memset(ans,0,sizeof(ans)); for(int i=1;i<=m;i++) { int x,y,z;scanf("%d %d %d",&x,&y,&z); update(x,y,z,1,1,n); } for(int i=1;i<=n;i++) printf("%d%c", ans[i], i == n ? '\n':' '); } return 0; } #include<iostream> #include<cstring> #include<cstdio> using namespace std; const int maxn=55555; int t[maxn<<2]; int ans[maxn],n,m; //只有左儿子和右儿子均被更新 void pushup(int rt) { t[rt]=t[rt<<1]&&t[rt<<1|1]; } void update(int x,int y,int z,int rt,int l,int r) { if(t[rt])return;//如果本区间已经更新，根据题目要求便不再更新 if(l==r)//更新到点 { if(l!=z&&x==l) //如果当前的点是获胜方，则不必进行更新， { ans[l]=z; t[rt]=1; } return;; } int m=(l+r)>>1; if(y<=m)update(x,y,z,rt<<1,l,m); else if(x>m) update(x,y,z,rt<<1|1,m+1,r); else{ update(x,m,z,rt<<1,l,m); update(m+1,y,z,rt<<1|1,m+1,r); } pushup(rt); } int main() { while(~scanf("%d%d",&n,&m)) { memset(t,0,sizeof(t)); memset(ans,0,sizeof(ans)); for(int i=1;i<=m;i++) { int x,y,z;scanf("%d%d%d",&x,&y,&z); update(x,y,z,1,1,n); } cout<<ans[1]; for(int i=2;i<=n;i++){ cout<<" "<<ans[i]; } printf("\n"); } return 0; }
