Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <unordered_map>
- #define maxn 300001
- #define smaxn 600
- #define F first
- #define S second
- #define mp make_pair
- #define pb push_back
- using namespace std;
- int bs;
- list<int> v;
- int in[maxn];
- unordered_map<int,int> pos;
- int n;
- struct Block{
- list<int>::iterator ini,fim;
- int qtd;
- Block(){
- fim=ini=v.end();
- qtd =0;
- }
- };
- Block sum[smaxn];
- int query(int l,int r) {
- auto it = sum[pos[l]].ini;
- while(*it !=l)it++;
- it++;
- int block = pos[*it];
- int ans=0;
- if(it != sum[block].ini){
- while(it !=sum[block].fim){
- if(*it == r) return ans;
- ans++;
- it++;
- }
- if(*it == r) return ans;
- ans++;
- it++;
- block++;
- }
- while(block<pos[r]){
- ans+=bs;
- block++;
- }
- it = sum[block].ini;
- while(*it !=r){
- ans++;
- it++;
- }
- return ans;
- }
- void insert(int p, int e) {
- int block = pos[e];
- auto it = sum[block].ini;
- //printf("%d %d\n",p,e );
- while(*it!=e)it++;
- it++;
- v.insert(it,p);
- if(p == *sum[block].fim)block++;
- pos[e] = block;
- while(sum[block].qtd== bs){
- pos[*sum[block].fim]++;
- sum[block+1].ini = sum[block].fim;
- sum[block].fim--;
- block++;
- }
- if(sum[block].qtd ==bs-1) sum[block].fim--;
- sum[block].qtd++;
- }
- int remove(int p) {
- int block = pos[p];
- auto it = sum[block].ini;
- while(*it!=p)it++;
- v.erase(it);
- if(p == *sum[block].ini) sum[block].ini--;
- while(sum[block].qtd == bs){
- pos[*sum[block+1].ini]--;
- sum[block].fim =sum[block+1].ini;
- sum[block+1].ini++;
- block++;
- }
- if(sum[block].qtd == 0)block--;
- sum[block].qtd--;
- }
- void build () {
- int block =0;
- for(int i=0;i<n;i++){
- v.push_back(in[i]);
- pos[i]=block;
- list<int>::iterator end = v.end();
- end--;
- if(sum[block].qtd == 0) sum[block].ini = end;
- sum[block].qtd++;
- if(sum[block].qtd == bs){
- sum[block].fim=end;
- block++;
- }
- }
- }
- void printlist(){
- for(auto it = v.begin();it!=v.end();it++){
- printf("%d ",*it );
- }
- printf("\n");
- }
- int main () {
- scanf("%d", &n);
- bs =sqrt(maxn);
- for (int i = 0; i < n; i++) {
- scanf("%d", in+i);
- }
- build();
- int q; scanf("%d", &q);
- while(q--) {
- //printlist();
- char c; scanf(" %c", &c);
- if (c == 'I') {
- int p, e; scanf("%d %d", &p, &e);
- insert(p,e);
- } else if (c == 'R') {
- int e; scanf("%d", &e);
- remove(e);
- } else {
- int a, b; scanf("%d %d", &a, &b);
- if(pos[a]>pos[b]){
- int aux =a;
- a = b;
- b = aux;
- }else if(pos[a] == pos[b]){
- for(auto it = sum[pos[a]].ini;it!=sum[pos[a]].fim;it++){
- if(*it == a)break;
- if(*it == b){
- int aux = a;
- a = b;
- b = aux;
- break;
- }
- }
- }
- printf("%d\n",query(a,b) );
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement