@OceanEye7年前
04/8
18:51
妈呀这题真卡时。
不得不承认这是我第二道用递归线段树AC的题目qwq太感动了
这题差不多是线段树的裸题了，，只需要bitset维护每一条线段上的颜色还有记得维护PushDown标记就好了。
其他都是细节问题，但是不知道为什么我加了读入优化之后就爆炸WA，，
所以只贴一份AC的无读入优化的代码好了qwq
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include <cstdio> #include <algorithm> #include <bitset> #include <iostream> using namespace std; const int NIL = 0; const int maxn = 100050; const int Root = 1; struct node { bitset <32> rec; int l,r; bool flag; }T[8*maxn]; int n,t,o,i,j; bitset <32> ans; void build(int l,int r,int k) { T[k].rec.set(1); T[k].l = l;T[k].r = r; if (l==r) return; int mid = (l+r) >> 1; build(l,mid,k<<1); build(mid+1,r,k<<1|1); } void PushUP(int x) { int lc = x<<1 , rc = x<<1|1; T[x].rec.reset(); for(int i=1;i<=t;i++) if(T[lc].rec.test(i) || T[rc].rec.test(i)) T[x].rec.set(i); if (T[x].rec.count() == 1) T[x].flag = true; } void insert(int l,int r,int c,int x) { if (T[x].l >= l && T[x].r <= r) { T[x].rec.reset(); T[x].rec.set(c); T[x].flag = true; return; } if (T[x].l==T[x].r || T[x].r < l || T[x].l > r) return; if(T[x].flag) { T[x<<1].rec.reset(); T[x<<1|1].rec.reset(); for(int i=1;i<=t;i++) if (T[x].rec.test(i)){ T[x<<1].rec.set(i); T[x<<1|1].rec.set(i); } T[x<<1].flag = true;T[x<<1|1].flag = true; T[x].flag = false; } insert(l,r,c,x<<1); insert(l,r,c,x<<1|1); PushUP(x); } void query(int l,int r ,int x) { if(T[x].l > r || T[x].r < l) return; if(T[x].l <= l || T[x].r >= r)if (T[x].flag) { for(int i=1;i<=t;i++) if (T[x].rec.test(i)) ans.set(i); return; } if (T[x].l >= l && T[x].r <= r) { for(int i=1;i<=t;i++) if (T[x].rec.test(i)) ans.set(i); return; } if (T[x].l==T[x].r) return; query(l,r,x<<1); query(l,r,x<<1|1); } int main() { std::ios::sync_with_stdio(false); cin >> n >> t >> o; build(1,n,Root); for(i=1;i<=o;i++) { char cmd = getchar(); while(cmd == '\n' || cmd == ' ') cmd = getchar(); if (cmd == 'C') { int l,r,c; cin >> l >> r >> c ; if (l > r) swap(l,r); insert(l,r,c,Root); } if (cmd == 'P') { int l,r; cin >> l >> r ; if (l > r) swap(l,r); ans.reset(); query(l,r,Root); cout << ans.count() << endl; } } return 0; } |