入门 6-单点插入-单点查询
typedef pair<int,int> PII; ll n,a[maxn]; ll blk,lazy[maxn],b[maxn],sum[maxn],tot; vector<int> vet[maxn]; void reBuild() { int p = 0; for(int i=1; i<=tot; i++) { for(int val : vet[i]) { a[++p] = val; } vet[i].clear(); } blk = sqrt(p); tot = ceil(1.0 * p / blk); for(int i=1; i<=p; i++) { b[i] = (i - 1) / blk + 1; vet[b[i]].push_back(a[i]); } } PII query(ll r) { for(int i=1; i<=tot; i++) { if(r > vet[i].size()) r -= vet[i].size(); else return {i,r-1}; } } void insert(ll l,ll r) { PII t = query(l); vet[t.first].insert(vet[t.first].begin() + t.second,r); if(vet[t.first].size() > 10 * blk) reBuild(); } int main() { n = read; for(int i=1; i<=n; i++) a[i] = read; blk = sqrt(n); tot = ceil(1.0*n / blk); for(int i=1; i<=n; i++) { b[i] = (i - 1) / blk + 1; vet[b[i]].push_back(a[i]); } for(int i=1; i<=n; i++) { int op = read,l = read,r = read,c = read; if(op == 0) insert(l,r); else { PII t = query(r); printf("%d\n",vet[t.first][t.second]); } } return 0; } /** 4 1 2 2 3 0 1 3 1 1 1 4 4 0 1 2 2 1 1 2 4 2 3 **/
入门 7-区间乘法-区间加法-单点查询
const int maxn = 1e5 + 7; const int mod = 10007; ll n,a[maxn]; ll blk,add[maxn],b[maxn],sum[maxn],mul[maxn]; void pushDown(int id) { for(int i=(id-1) * blk + 1; i<=min(id * blk,n); i++) { a[i] = (a[i] * mul[id] % mod + add[id] + mod) % mod; } mul[id] = 1; add[id] = 0; } void add_mul(int l,int r,ll val,int op) { pushDown(b[l]); for(int i=l; i<=min(b[l]*blk,1LL*r); i++) { if(op) a[i] = (a[i] * val) % mod; else a[i] = (a[i] + val) % mod; } if(b[l] != b[r]) { pushDown(b[r]); for(int i=(b[r]-1)*blk + 1; i<=r; i++) { if(op) a[i] = (a[i] * val) % mod; else a[i] = (a[i] + val) % mod; } } for(int i=b[l]+1; i<=b[r]-1; i++) { if(op) mul[i] = (mul[i] * val) % mod,add[i] = (add[i] * val) % mod; else add[i] = (add[i] + val) % mod; } } ll query(int r) { ll ret = 0; ret = (a[r] * mul[b[r]] % mod + add[b[r]]) % mod; return ret; } int main() { n = read; for(int i=1; i<=n; i++) a[i] = read; blk = sqrt(n); for(int i=1; i<=n; i++) { b[i] = (i - 1) / blk + 1; mul[b[i]] = 1; add[b[i]] = 0; } for(int i=1; i<=n; i++) { int op = read,l = read,r = read,c = read; if(op == 2) { printf("%lld\n",query(r)); } else { add_mul(l,r,c,op); } } return 0; } /** 7 1 2 2 3 9 3 2 0 1 3 1 2 1 3 1 1 1 4 4 0 1 7 2 1 2 6 4 1 1 6 5 2 2 6 4 3 100 **/
入门 8-区间修改-区间查询
ll n,a[maxn]; ll blk,add[maxn],b[maxn],upd[maxn]; void reset(int id) { if(upd[id] == -1) return ; for(int i=(id-1) * blk+1; i<=min(id*blk,n); i++) { a[i] = upd[id]; } upd[id] = -1; } ll getSet(int l,int r,ll val) { ll ans = 0; reset(b[l]); for(int i=l; i<=min(b[l]*blk,1LL*r); i++) { ans += a[i] == val; a[i] = val; } if(b[l] != b[r]) { reset(b[r]); for(int i=(b[r]-1)*blk + 1; i<=r; i++) { ans += a[i] == val; a[i] = val; } } for(int i=b[l]+1; i<=b[r]-1; i++) { if(upd[i] == -1) { for(int j=(i-1)*blk+1; j<=i*blk; j++) { ans += a[j] == val; } } else ans += upd[i] == val?blk:0; upd[i] = val; } return ans; } int main() { n = read; for(int i=1; i<=n; i++) a[i] = read; blk = sqrt(n); for(int i=1; i<=n; i++) { b[i] = (i - 1) / blk + 1; upd[b[i]] = -1; } for(int i=1; i<=n; i++) { int l = read,r = read,c = read; ll ans = getSet(l,r,c); printf("%lld\n",ans); } return 0; } /** 4 1 2 2 4 1 3 1 1 4 4 1 2 2 1 4 2 1 1 0 2 **/
入门 9-区间查询众数
#define Clear(x,val) memset(x,val,sizeof x) ll n,a[maxn],ans[2007][2007],b[maxn],blk,cnt[maxn],num; vector<int> vet[maxn]; map<int,int> vis,val; void get(int id) { Clear(cnt,0); int mx = 0,res = 0; for(int i=(id-1) * blk + 1; i<=n; i++) { int to = b[i];///cur is the b[i]-th blk ++ cnt[a[i]];/// the amt ++ if(cnt[a[i]] > mx || (cnt[a[i]] == mx && val[a[i]] < val[res])) { res = a[i];/// set the cur mx value mx = cnt[a[i]]; } ans[id][to] = res;/// from blk id -> blk to the ans = res } } int getNum(int l,int r,int x) { int ret = 0; ret = upper_bound(vet[x].begin(),vet[x].end(),r) - lower_bound(vet[x].begin(),vet[x].end(),l);/// amount of x return ret; } ll query(int l,int r) { ll ret = ans[b[l] + 1][b[r] - 1];// center blks int mx = getNum(l,r,ret);// get the amount of this for(int i=l; i<=min(r*1LL,b[l]*blk); i++) { int amt = getNum(l,r,a[i]); if(amt > mx || (amt == mx && val[a[i]] < val[ret])) { ///val[ret] ret = a[i]; mx = amt; } } if(b[l] != b[r]) { for(int i = (b[r] - 1) * blk + 1; i<=r; i++) { int amt = getNum(l,r,a[i]); if(amt > mx || (amt == mx && val[a[i]] < val[ret])) { ret = a[i]; mx = amt; } } } return val[ret]; } int main() { n = read; blk = sqrt(n); blk = 80; for(int i=1; i<=n; i++) { a[i] = read; b[i] = (i - 1) / blk + 1; if(!vis[a[i]]) { vis[a[i]] = ++ num; val[num] = a[i];///¶ÔӦϠ} a[i] = vis[a[i]]; vet[a[i]].push_back(i); } for(int i=1; i<=b[n]; i++) get(i); /// get the i-th blk for(int i=1; i<=n; i++) { int l = read,r = read; if(l > r) swap(l,r); ll ans = query(l,r); printf("%lld\n",ans); } return 0; } /** 4 1 2 2 4 1 2 1 4 2 4 3 4 1 2 2 2 **/
