求卡空间
查看原帖
求卡空间
826774
Little_Fox_Fairy楼主2024/11/29 17:06

感觉已经优化完了。

已优化的点：

  1. CDQ 的归并排序。
  2. 多余的数组。
  3. assign 里面 vector 换临时数组。
#include<bits/stdc++.h>
using namespace std;
namespace fast_IO {
#define IOSIZE 100000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
const int N=8e5+10;
const int M=1e5+10;
struct node {
	int op,time;
	int a,b;short type;
}e[N];

int n,pre[N],m,res[M],lst[N];
int del[M];
bitset<M> has;
unordered_map<int,int> uni;
int tim;
namespace BIT {
	int t[M];
	inline int lowbit(int x) {return x&-x;}
	inline void update(int x,int val) {
		while (x<=n) {
			t[x]+=val;
			x+=lowbit(x);
		}
		return ;
	}
	inline int query(int x) {
		int ans=0;
		while (x) {
			ans+=t[x];
			x-=lowbit(x);
		}
		return ans;
	}
}using namespace BIT;
namespace Chotholly_Willem {
	struct Chotholly {
		int l,r;
		mutable int val;
		bool operator <(const Chotholly &x) const {return l<x.l;}
	};
	set<Chotholly> s,se[N];
	inline auto Insert(int l,int r,int val) {
		se[val].insert({l,r,val});
		return s.insert({l,r,val}).first;
	}
	inline void Delete(int l,int r,int val) {
		s.erase({l,r,val});
		se[val].erase({l,r,val});
		return ;
	}
	inline auto split(int pos) {
		auto it=s.lower_bound({pos,0,0});
		if (it!=s.end() and it->l==pos) return it;
		it--;
		if (it->r<pos) return s.end();
		int l=it->l,r=it->r,val=it->val;
		Delete(l,r,val);
		Insert(l,pos-1,val);
		return Insert(pos,r,val);
	}
    inline int Pre(int pos) {
        auto it=--s.upper_bound({pos,0,0});
        if (it->l<pos) return pos-1;
        else {
            auto itl=se[it->val].lower_bound({pos,0,0});
            if (itl!=se[it->val].begin()) return (--itl)->r;
            return 0;
        }
    }
	inline void assign(int l,int r,int val,int time) {
		auto itr=split(r+1),itl=split(l);
		int len=0;
		for (auto it=itl;it!=itr;it++) {
			if (it!=itl) del[++len]=it->l;
			auto itt=se[it->val].upper_bound(*it);
			if (itt!=se[it->val].end()) del[++len]=itt->l;
			auto dele=it;
			se[it->val].erase(*dele);
		}
		del[++len]=l;
		s.erase(itl,itr);
		Insert(l,r,val);
		auto itt=se[val].upper_bound({l,r,val});
		if (itt!=se[val].end()) del[++len]=itt->l;
		for (int i=1;i<=len;i++) {
			e[++m].op=0,e[m].a=del[i],e[m].b=pre[del[i]],e[m].time=time,e[m].type=-1;
			pre[del[i]]=Pre(del[i]);
			e[++m].op=0,e[m].a=del[i],e[m].b=pre[del[i]],e[m].time=time,e[m].type=1;
		}
		return ;
	}
}using namespace Chotholly_Willem;
inline void CDQ(int l,int r) {
	if (l==r) return ;
	int mid=l+r>>1,p=l,q=mid+1,len=0;
	CDQ(l,mid),CDQ(mid+1,r);
//	while (p<=mid and q<=r) {
//		if (e[p].b<e[q].b) {
//			if (e[p].op==0) {
//				update(e[p].a,e[p].type);
//			}
//			tmp[++len]=e[p++];
//		}
//		else {
//			if (e[q].op==1) {
//				res[e[q].time]+=e[q].type*query(e[q].a);
//			}
//			tmp[++len]=e[q++];
//		}
//	}
//	while (p<=mid) {
//		if (e[p].op==0) {
//			update(e[p].a,e[p].type);
//		}
//		tmp[++len]=e[p++];
//	}
//	while (q<=r) {
//		if (e[q].op==1) {
//			res[e[q].time]+=e[q].type*query(e[q].a);
//		}
//		tmp[++len]=e[q++];
//	}
	sort(e+l,e+mid+1,[](node x,node y){return x.b==y.b?x.a<y.a:x.b<y.b;});
	sort(e+mid+1,e+r+1,[](node x,node y){return x.b==y.b?x.a<y.a:x.b<y.b;});
	int j=l;
	for (int i=mid+1;i<=r;i++) {
		while (j<=mid and e[j].b<e[i].b) {
			if (e[j].op==0) {
				update(e[j].a,e[j].type);
			}
			j++; 
		}
		if (e[i].op==1) {
			res[e[i].time]+=e[i].type*query(e[i].a);
		}
	}
	for (int i=l;i<j;i++) {
		if (e[i].op==0) {
			update(e[i].a,-e[i].type);
		}
	}
	return ;
}
signed main() {
	int _;
	cin>>n>>_;
	for (int i=1;i<=n;i++) {
		int x;cin>>x;
		if (!uni[x]) uni[x]=++tim;
		x=uni[x];pre[i]=lst[x];lst[x]=i;
		e[++m].op=0,e[m].time=0,e[m].a=i,e[m].b=pre[i],e[m].type=1;
		Insert(i,i,x);
	}
	for (int i=1;i<=_;i++) {
		char op;cin>>op;
		int l,r,val;
		if (op=='2') has[i]=1;
		if (op=='2') {
			cin>>l>>r;
			e[++m].op=1,e[m].time=i,e[m].a=l-1,e[m].b=l,e[m].type=-1;
			e[++m].op=1,e[m].time=i,e[m].a=r,e[m].b=l,e[m].type=1;
		}
		else if (op=='1') {
			cin>>l>>r>>val;
			if (!uni[val]) uni[val]=++tim;
			val=uni[val];
			assign(l,r,val,i);
//			e[++m].op=0,e[m].time=i,e[m].a=l,e[m].b=Pre(val[l],l),e[m].type=-1,e[m].idx=++cnt;
//			e[++m].op=0,e[m].time=i,e[m].a=l,e[m].b=Pre(r,l),e[m].type=1,e[m].idx=++cnt;
//			if (Nex(val[l],l)) {
//				int next=Nex(val[l],l);
//				e[++m].op=0,e[m].time=i,e[m].a=next,e[m].b=Pre(val[next],next),e[m].type=-1,e[m].idx=++cnt;
//				e[++m].op=0,e[m].time=i,e[m].a=next,e[m].b=Pre(val[l],l),e[m].type=1,e[m].idx=++cnt;
//			}
//			if (Nex(r,l-1)) {
//				int next=Nex(r,l-1);
//				e[++m].op=0,e[m].time=i,e[m].a=next,e[m].b=Pre(val[next],next),e[m].type=-1,e[m].idx=++cnt;
//				e[++m].op=0,e[m].time=i,e[m].a=next,e[m].b=l,e[m].type=1,e[m].idx=++cnt;
//			}
//			se[val[l]].erase(l),se[r].insert(l);
//			val[l]=r;
		}
	}
//	sort(e+1,e+m+1,[](node x,node y){return x.idx<y.idx;});
	CDQ(1,m);
	for (int i=1;i<=_;i++) {
		if (has[i]) {
			cout<<res[i]<<endl;
		}
	}
	return (0-0);
}
2024/11/29 17:06