【題目描述】

給出一個長為 n 的數列，以及 n 個操作，操作涉及區間詢問等于一個數 c 的元素，并將這個區間的所有元素改為 c。

【輸入格式】

第一行輸入一個數字 n。

第二行輸入 n?個數字，第 i 個數字為 ai，以空格隔開。

接下來輸入 n 行詢問，每行輸入三個數字 l、r、c，以空格隔開。

表示先查詢位于 [l,r] 的數字有多少個是 c，再把位于 [l,r] 的數字都改為 c。

【輸出格式】

對于每次詢問，輸出一行一個數字表示答案。

【樣例】

樣例輸入
4
1 2 2 4
1 3 1
1 4 4
1 2 2
1 4 2

樣例輸出
1
1
0
2

【數據范圍與提示】

對于 100%?的數據，1<=n<=100000,-2^31<=other,ans<=2^31-1。

【源代碼】

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 10000+7; const int N = 1000000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std;int n; int block,sum;//block為塊的長度,sum為塊的個數 int a[N];//存放數列元素 int pos[N];//pos記錄第i個元素在第幾個塊中 int flag[N];//標記整塊是否值相同 void init(int n){block=sqrt(n);//塊的長度for(int i=1;i<=n;i++)//第i個元素在第幾塊中pos[i]=(i-1)/block+1;memset(flag,-1,sizeof(flag));//標記初始化 } void reset(int x){//更新不完整塊的值if(flag[pos[x]]==-1)return;else{for(int i=(pos[x]-1)*block+1;i<=min(pos[x]*block,n);i++)//更新元素a[i]=flag[pos[x]];}flag[pos[x]]=-1;//更新標記 } int query(int L,int R,int x){int res=0;reset(L);//更新左端不完整塊for(int i=L;i<=min(pos[L]*block,R);i++){//左邊的邊角料if(a[i]==x)res++;a[i]=x;}if(pos[L]!=pos[R]){//存在右區間才遍歷，防止重復計算reset(R);//更新右端不完整塊for(int i=(pos[R]-1)*block+1;i<=R;i++){//右邊的邊角料if(a[i]==x)res++;a[i]=x;}}for(int i=pos[L]+1;i<=pos[R]-1;i++){//中間的整塊if(flag[i]==-1){//沒有標記，暴力查詢for(int j=(i-1)*block+1;j<=i*block;j++){if(a[j]==x)res++;a[j]=x;}}else if(flag[i]==x)//整塊相等res+=block;flag[i]=x;//更新標記}return res; } int main(){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);init(n);for(int i=1;i<=n;i++){int left,right,x;scanf("%d%d%d",&left,&right,&x);printf("%d\n",query(left,right,x));}return 0; }

?

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的数列分块入门 8（LibreOj-6284）的全部內容，希望文章能夠幫你解決所遇到的問題。

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