题意: 10 给定一个长度为N(N <= 100000)的数列Si，紧接着Q(Q <= 100000)条操作，操作 11 形式有两种： 12 1. "C A B C" 将A到B的数都染成C这种颜色。 13 2. "P A B" 输出A和B之间不同颜色的数目。
不知道为什么把down写成 just a hook 那题一样就会错
#include<cstdio> #include<algorithm> using namespace std; //input #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m); #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define LL long long #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define N 200005 #define lson L,m,pos<<1 #define rson m+1,R,pos<<1|1 int t[N<<2]; int c[N<<2]; void up(int pos) { t[pos]=(t[pos<<1]|t[pos<<1|1]); } void down(int pos,int m) { if(c[pos]) { c[pos<<1]=c[pos<<1|1]=c[pos]; //t[pos<<1]=c[pos]*(m-(m>>1) ); //t[pos<<1|1]=(m>>1)*c[pos]; t[pos<<1]=t[pos<<1|1]=t[pos]; c[pos]=0; } } void build(int L,int R ,int pos) { c[pos]=0; if(L==R) { t[pos]=1; return ; } int m=(L+R)>>1; build(lson); build(rson); up(pos); } void update(int l,int r,int v,int L,int R,int pos) { if(l<=L&&r>=R) { t[pos]=v; c[pos]=1; return ; } down(pos,R-L+1); int m=(L+R)>>1; if(l<=m) update(l,r,v,lson); if(r>m) update(l,r,v,rson); up(pos); } int query(int l,int r,int L,int R,int pos) { int ans=0; if(l<=L&&r>=R) return t[pos]; down(pos,R-L+1); int m=(L+R)>>1; if(r<=m)ans|=query(l,r,lson); else if(l>m) ans|=query(l,r,rson); else ans|=query(l,r,lson)|query(l,r,rson); return ans; } int main() { int n,t,m; while(RIII(n,t,m)==3) { build(1,n,1); char str[5]; int a,b,c; while(m--) { RS(str); if(str[0]==‘C‘) { RIII(a,b,c); update(a,b,1<<(c-1),1,n,1); } else { RII(a,b); if(a>b)swap(a,b); int temp=query(a,b,1,n,1); int ans=0; while(temp) { if(temp%2) ans++; temp=(temp>>1); } printf("%d\n",ans); } } } }
附上另一种较好的代码 对懒惰标记的理解更深一步了‘
#include <iostream> #include <cstdio> #include <cstring> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <cmath> #include <algorithm> using namespace std; const double eps = 1e-6; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int MOD = 1000000007; #define ll long long #define CL(a,b) memset(a,b,sizeof(a)) #define MAXN 100010 struct node { int l,r,s; } t[MAXN<<2]; int L,O,T; int sum[33];//因为颜色数不多，可以用一个数组来装；1表示该区间有该颜色，0反之 void build(int l, int r, int i) { t[i].l = l; t[i].r = r; t[i].s = 1; if(l == r) return ; int mid = (l+r)>>1; build(l, mid, i<<1); build(mid+1, r, i<<1|1); } void update(int l, int r, int m, int i) { if(t[i].s == m) return ; if(t[i].l == l && t[i].r == r) { t[i].s = m; return ; } if(t[i].s != -1) { t[i<<1].s = t[i<<1|1].s = t[i].s; t[i].s = -1; } int mid = (t[i].l+t[i].r)>>1; if(l > mid) update(l, r, m, i<<1|1); else if(r <= mid) update(l, r, m, i<<1); else { update(l, mid, m, i<<1); update(mid+1, r, m, i<<1|1); } } void query(int l, int r, int i) { if(t[i].s != -1)//如果纯色把该颜色标记 { sum[t[i].s] = 1; return ; } else//否则继续查询子节点 { int mid = (t[i].l+t[i].r)>>1; if(l > mid) query(l, r, i<<1|1); else if(r <= mid) query(l, r, i<<1); else { query(l, mid, i<<1); query(mid+1, r, i<<1|1); } } } int main() { char ch; int a,b,c; while(scanf("%d%d%d",&L,&T,&O)==3) { build(1, L, 1); while(O--) { getchar(); scanf("%c",&ch); if(ch == ‘C‘) { scanf("%d%d%d",&a,&b,&c); update(a, b, c, 1); } int ans = 0; if(ch == ‘P‘) { CL(sum, 0);//每次查询之前清零 scanf("%d%d",&a,&b); query(a, b, 1); for(int i=1; i<=T; i++)//统计出现过的颜色数 if(sum[i]) ans++; printf("%d\n",ans); } } } return 0; }
原文：https://www.cnblogs.com/bxd123/p/10489213.html