題目鏈接：點擊查看

題目大意：給出一個二維平面坐標系，需要完成四種操作：

0：刪除所有點

1 $xyc$：在點 $(x,y)$ 處添加顏色 $c$

2 $xy1y2$：查詢左下角為 $(1,y1)$ 右上角為 $(x,y2)$ 矩陣內有多少種不同的顏色

題目分析：點數和詢問都是 $1e5$ 級別的，從矩陣的左側只能等于 $1$ 入手，將問題轉換為求 $x$ 的前綴和 $y$ 的區間

那么自然而然想到開 $50$ 個樹狀數組套線段樹單獨維護每個顏色，詢問時單獨查詢即可，但這樣的空間復雜度有點炸

考慮優化，因為顏色至多有 $50$ 種，所以將顏色狀壓，將線段樹求 “頂點個數” 的操作轉換為求 “按位或” 的操作，這樣只需要開一個樹狀數組套線段樹即可，時間復雜度是 $O(nlo{g}^{2}n)$ 的

上面是最簡單的思路，但是實現起來有一定的困難，所以考慮另一種思路

還是將每種顏色獨立，每次查詢我們只需要確定，是否存在著一個點 $(xx,yy)$，滿足 $xx>=1\&\&xx<=x\&\&yy>=y1\&\&yy<=y2$ 即可，不難發現對于 $x$ 坐標而言，有一個條件永遠都滿足的，所以我們不妨找出區間 $[y1,y2]$內的點，$x$ 軸的最小值，判斷其是否小于等于閾值即可，于是將題目轉換為了區間求最小值，單點更新的題目了

然后就是 $y$ 軸的坐標比較大，可以選擇離散化或動態開點，時間復雜度 $O(nlogn)$

代碼：
動態開點：

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=1000000; const int N=1e6+100; struct Node {int l,r,mmin; }tree[N]; int cnt,root[51]; bool flag; int newnode() {cnt++;tree[cnt].l=tree[cnt].r=0;tree[cnt].mmin=inf;return cnt; } void update(int &k,int l,int r,int pos,int val) {if(!k) {k=newnode();}tree[k].mmin=min(tree[k].mmin,val);if(l==r) {return;}int mid=(l+r)>>1;if(pos<=mid) {update(tree[k].l,l,mid,pos,val);} else {update(tree[k].r,mid+1,r,pos,val);} } void query(int k,int l,int r,int ql,int qr,int val) {if(!k||l>qr||r<ql||flag) {return;}if(l>=ql&&r<=qr) {if(tree[k].mmin<=val) {flag=true;}return;}int mid=(l+r)>>1;query(tree[k].l,l,mid,ql,qr,val);query(tree[k].r,mid+1,r,ql,qr,val);} int cal(int x,int y1,int y2) {int ans=0;for(int i=0;i<=50;i++) {flag=0;query(root[i],1,inf,y1,y2,x);ans+=flag;}return ans; } void init() {cnt=-1;newnode();for(int i=0;i<=50;i++) {root[i]=0;} } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int op;while(scanf("%d",&op)!=EOF&&op!=3) {if(op==0) {init();} else if(op==1) {int x,y,c;read(x),read(y),read(c);update(root[c],1,inf,y,x);} else if(op==2) {int x,y1,y2;read(x),read(y1),read(y2);printf("%d\n",cal(x,y1,y2));}}return 0; }

樹狀數組套線段樹（動態開點）

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; int cnt; struct Seg {struct Node {int l,r;LL sum;}tree[150010*20*20];int newnode() {cnt++;tree[cnt].l=tree[cnt].r=0;tree[cnt].sum=0;return cnt;}void update(int &k,int l,int r,int pos,LL val) {if(!k) {k=newnode();}tree[k].sum|=val;if(l==r) {return;}int mid=(l+r)>>1;if(pos<=mid) {update(tree[k].l,l,mid,pos,val);} else {update(tree[k].r,mid+1,r,pos,val);}}LL query(int k,int l,int r,int ql,int qr) {if(!k||l>qr||r<ql) {return 0;}if(l>=ql&&r<=qr) {return tree[k].sum;}int mid=(l+r)>>1;return query(tree[k].l,l,mid,ql,qr)|query(tree[k].r,mid+1,r,ql,qr);} }SEG; struct Bit {int root[N];void add(int x,int y,LL val) {for(int i=x;i<N;i+=lowbit(i)) {SEG.update(root[i],1,1e6,y,val);}}LL ask(int x,int y1,int y2) {LL ans=0;for(int i=x;i>0;i-=lowbit(i)) {ans|=SEG.query(root[i],1,1e6,y1,y2);}return ans;} }BIT; int cal(LL x) {int ans=0;while(x) {ans+=x&1;x>>=1;}return ans; } void init() {cnt=-1;SEG.newnode();memset(BIT.root,0,sizeof(BIT.root)); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int op;while(scanf("%d",&op)!=EOF&&op!=3) {if(op==0) {init();} else if(op==1) {int x,y,c;read(x),read(y),read(c);BIT.add(x,y,1LL<<c);} else if(op==2) {int x,y1,y2;read(x),read(y1),read(y2);printf("%d\n",cal(BIT.ask(x,y1,y2)));}}return 0; }

總結

以上是生活随笔為你收集整理的HDU - 6183 Color it(动态开点线段树/树状数组套动态开点线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。