题目
代码
//分块可以AC 20个点的块长， sqrt(n)*5#include<bits/stdc++.h>
using namespace std;int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n; cin>>n;vector<int> a(n+1,0);//分块int len = sqrt(n)*5; //块长int k = (n%len==0)?n/len:n/len+1;//块数vector<int> block[k+1]; //本体vector<int> belong(n+1,0);int blockNum = 0;for(int i=1;i<=n;i++){ //分块cin>>a[i];blockNum=(i-1)/len+1;belong[i]=blockNum;block[blockNum].push_back(a[i]);}for(int i=1;i<=k;i++){ //块排序sort(block[i].begin(),block[i].end(),less<int>());}//输入操作int m; cin>>m;vector<vector<int>> op(m,vector<int>(4,0));for(int i=0;i<m;i++){cin>>op[i][0];cin>>op[i][1]>>op[i][2];if(op[i][0]==2)cin>>op[i][3];}//执行vector<int> res;for(int i = 0; i < m; i++){int num1=op[i][1], num2=op[i][2], num3=op[i][3];if(op[i][0]==1){ //修改auto it=lower_bound(block[belong[num1]].begin(),block[belong[num1]].end(),a[num1]);block[belong[num1]].erase(it);it=lower_bound(block[belong[num1]].begin(),block[belong[num1]].end(),num2);if(it==block[belong[num1]].end())block[belong[num1]].push_back(num2);else block[belong[num1]].insert(it,num2);a[num1] = num2;}else{ //查询int count = 0, mid = a[num3];//先查左右两端分块中满足条件的元组数,因为num1和num2所在的块不一定一整块都参与比较for(int j=num1;j<=min(num2,belong[num1]*len);j++){if(a[j]<mid)count++;}if(belong[num1]!=belong[num2]){for(int j=(belong[num2]-1)*len+1;j<=num2;j++){if(a[j]<mid)count++;}}//区间查询,用二分法查询每个块中小于a[p]的元素个数for(int j=belong[num1]+1;j<=belong[num2]-1;j++){count+=lower_bound(block[j].begin(),block[j].end(),a[num3])-block[j].begin();}res.push_back(count+1);}}for(auto &&num:res)cout<<num<<" ";return 0;
}
