UVa 12345. Dynamic len(set(a[L:R]))<\/a><\/p>\n\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = int(1e4) + 9;\r\nint A[N], AA[N], n, m;\r\n\r\nnamespace ST{\r\n\r\n#define lx l[x]\r\n#define rx r[x]\r\n#define ly l[y]\r\n#define ry r[y]\r\n#define ml (ll + rr >> 1)\r\n#define mr (ml + 1)\r\n\r\n const int NN = N*10*10*7 + 9;\r\n int l[NN], r[NN], c[NN], tot;\r\n\r\n int new_node(){\r\n return ++tot;\r\n }\r\n\r\n int Add(int y, int p, int d){\r\n int x = new_node(), root = x; int ll = 0, rr = n;\r\n \/\/cout << p << " " << d <<endl;\r\n\r\n c[x] = c[y] + d;\r\n while (ll < rr){\r\n if (p < mr){\r\n lx = new_node(), rx = ry;\r\n x = lx, y = ly, rr = ml;\r\n }\r\n else {\r\n lx = ly, rx = new_node();\r\n x = rx, y = ry, ll = mr;\r\n }\r\n c[x] = c[y] + d;\r\n }\r\n return root;\r\n }\r\n\r\n int Sum(int x, int p){ \/\/ \u5c0f\u4e8e x\r\n int z = 0, ll = 0, rr = n; while (ll < rr){\r\n if (p < mr) x = lx, rr = ml;\r\n else z += c[lx], x = rx, ll = mr;\r\n }\r\n return z;\r\n }\r\n}\r\n\r\nnamespace BIT{\r\n int C[N], a, b;\r\n\r\n void Add(int x, int p, int d){\r\n for (;x<=n;x+=low_bit(x)) C[x] = ST::Add(C[x], p, d);\r\n }\r\n void Modify(int x, int& p, int pp){\r\n Add(x, p, -1); Add(x, pp, 1); p = pp;\r\n }\r\n int Sum(int x){\r\n int z = 0; for (;x;x^=low_bit(x)) z += ST::Sum(C[x], a);\r\n return z;\r\n }\r\n int Sum(int _a, int _b){\r\n a = _a, b = _b;\r\n return Sum(b) - Sum(a-1);\r\n }\r\n}\r\n\r\nconst int AMAX = int(1e6) + 9;\r\nSI H[AMAX];\r\n\r\nvoid print(){\r\n REP_1(i, n) cout << A[i] << " "; puts("");\r\n REP_1(i, n) cout << AA[i] << " "; puts("");\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n RD(n, m); REP_1(i, n){\r\n RD(A[i]); SI &s = H[A[i]]; if (s.empty()) s.insert(0);\r\n BIT::Add(i, AA[i] = *s.rbegin(), 1); s.insert(i);\r\n }\r\n\r\n DO(m){\r\n char cmd; int a, b; RC(cmd); RD(a, b);\r\n if (cmd == 'Q'){\r\n OT(BIT::Sum(a, b));\r\n }\r\n else{\r\n if (A[a] == b) continue;\r\n SI::iterator it; SI &sa = H[A[a]], &sb = H[b]; if (sb.empty()) sb.insert(0);\r\n it = sa.upper_bound(a); if (it != sa.end()) BIT::Modify(*it, AA[*it], AA[a]);\r\n it = sb.upper_bound(a); if (it != sb.end()) BIT::Modify(*it, AA[*it], a);\r\n --it; BIT::Modify(a, AA[a], *it);\r\n sa.erase(a); sb.insert(a); A[a] = b;\r\n }\r\n }\r\n}\r\n\r\n<\/pre>\n\r\nstruct BITT{\r\n map<int, int> C;\r\n void Add(int x, int d){\r\n ++x;\r\n for (;x<=n;x+=low_bit(x)) C[x] += d;\r\n }\r\n int Sum(int x){\r\n int z = 0; for (;x;x^=low_bit(x)) z += C[x];\r\n return z;\r\n }\r\n};\r\n\r\nnamespace BIT{\r\n BITT C[N]; int a, b;\r\n\r\n void Add(int x, int p, int d){\r\n for (;x<=n;x+=low_bit(x)) C[x].Add(p, d);\r\n }\r\n void Modify(int x, int& p, int pp){\r\n Add(x, p, -1); Add(x, pp, 1); p = pp;\r\n }\r\n int Sum(int x){\r\n int z = 0; for (;x;x^=low_bit(x)) z += C[x].Sum(a);\r\n return z;\r\n }\r\n int Sum(int _a, int _b){\r\n a = _a, b = _b;\r\n return Sum(b) - Sum(a-1);\r\n }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[22],"tags":[],"class_list":["post-1077","post","type-post","status-publish","format-standard","hentry","category-bzoj"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-hn","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1077","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=1077"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1077\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1077"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1077"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1077"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}