社区讨论

悬 rmb，求卡常

折折雾赴海
P3157[CQOI2011] 动态逆序对参与者 6已保存回复 52

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
52 条
当前快照
1 份
快照标识符
@mhjaqtrm
此快照首次捕获于
2025/11/03 23:30
4 个月前
此快照最后确认于
2025/11/04 06:06
4 个月前
查看原帖
代码是过的，单纯想看看有没有更好的卡常方法，如果最高点能卡进 450ms450ms 就 1r，300ms300ms 就 2r，卡进 500ms500ms 就关，不能用过于没有稳定性的方法，其余我自行评判，代码在这里：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
static int a[N],p[N],bl[N],st[N],ed[N],tot;
const int mx=900;
static bool act[N];
static vector<int>v[mx];
static long long ans;
static int d[N];
namespace Fread
{
	const int SIZE = 1 << 16;
	char buf[SIZE], *S, *T;
	inline char getchar() { if (S == T) { T = (S = buf) + fread(buf, 1, SIZE, stdin); if (S == T) return '\n'; } return *S++; }
}
using namespace Fread;
namespace Fwrite
{
	const int SIZE = 1 << 16;
	char buf[SIZE], *S = buf, *T = buf + SIZE;
	inline void flush() { fwrite(buf, 1, S - buf, stdout); S = buf; }
	inline void putchar(char c) { *S++ = c; if (S == T) flush(); }
	struct NTR { ~NTR() { flush(); } } ztr;
}
using namespace Fwrite;
#define getchar Fread::getchar
#define putchar Fwrite::putchar
namespace Fastio
{
	struct Reader
	{
		template <typename T> Reader& operator >> (T &x)
		{
			x = 0;
			short f = 1;
			char c = getchar();
			while (c < '0' || c > '9') { if (c == '-') f *= -1; c = getchar(); }
			while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
			x *= f;
			return *this;
		}
		Reader& operator >> (double &x)
		{
			x = 0;
			double t = 0;
			short f = 1, s = 0;
			char c = getchar();
			while ((c < '0' || c > '9') && c != '.') { if (c == '-') f *= -1; c = getchar(); }
			while (c >= '0' && c <= '9' && c != '.') x = x * 10 + (c ^ 48), c = getchar();
			if (c == '.') c = getchar();
			else { x *= f; return *this; }
			while (c >= '0' && c <= '9') t = t * 10 + (c ^ 48), s++, c = getchar();
			while (s--) t /= 10.0;
			x = (x + t) * f;
			return *this;
		}
		Reader& operator >> (long double &x)
		{
			x = 0;
			long double t = 0;
			short f = 1, s = 0;
			char c = getchar();
			while ((c < '0' || c > '9') && c != '.') { if (c == '-') f *= -1; c = getchar(); }
			while (c >= '0' && c <= '9' && c != '.') x = x * 10 + (c ^ 48), c = getchar();
			if (c == '.') c = getchar();
			else { x *= f; return *this; }
			while (c >= '0' && c <= '9') t = t * 10 + (c ^ 48), s++, c = getchar();
			while (s--) t /= 10.0;
			x = (x + t) * f;
			return *this;
		}
		Reader& operator >> (__float128 &x)
		{
			x = 0;
			__float128 t = 0;
			short f = 1, s = 0;
			char c = getchar();
			while ((c < '0' || c > '9') && c != '.') { if (c == '-') f *= -1; c = getchar(); }
			while (c >= '0' && c <= '9' && c != '.') x = x * 10 + (c ^ 48), c = getchar();
			if (c == '.') c = getchar();
			else { x *= f; return *this; }
			while (c >= '0' && c <= '9') t = t * 10 + (c ^ 48), s++, c = getchar();
			while (s--) t /= 10.0;
			x = (x + t) * f;
			return *this;
		}
		Reader& operator >> (char &c)
		{
			c = getchar();
			while (c == ' ' || c == '\n' || c == '\r') c = getchar();
			return *this;
		}
		Reader& operator >> (char *str)
		{
			int len = 0;
			char c = getchar();
			while (c == ' ' || c == '\n' || c == '\r') c = getchar();
			while (c != ' ' && c != '\n' && c != '\r') str[len++] = c, c = getchar();
			str[len] = '\0';
			return *this;
		}
		Reader& operator >> (string &str)
		{
			str.clear();
			char c = getchar();
			while (c == ' ' || c == '\n' || c == '\r') c = getchar();
			while (c != ' ' && c != '\n' && c != '\r') str.push_back(c), c = getchar();
			return *this;
		}
		Reader() {}
	} cin;
	const char endl = '\n';
	struct Writer
	{
		const int Setprecision = 6;
		typedef int mxdouble;
		template <typename T> Writer& operator << (T x)
		{
			if (x == 0) { putchar('0'); return *this; }
			if (x < 0) putchar('-'), x = -x;
			static short sta[40];
			short top = 0;
			while (x > 0) sta[++top] = x % 10, x /= 10;
			while (top > 0) putchar(sta[top] + '0'), top--;
			return *this;
		}
		Writer& operator << (double x)
		{
			if (x < 0) putchar('-'), x = -x;
			mxdouble _ = x;
			x -= (double)_;
			static short sta[40];
			short top = 0;
			while (_ > 0) sta[++top] = _ % 10, _ /= 10;
			if (top == 0) putchar('0');
			while (top > 0) putchar(sta[top] + '0'), top--;
			putchar('.');
			for (int i = 0; i < Setprecision; i++) x *= 10;
			_ = x;
			while (_ > 0) sta[++top] = _ % 10, _ /= 10;
			for (int i = 0; i < Setprecision - top; i++) putchar('0');
			while (top > 0) putchar(sta[top] + '0'), top--;
			return *this;
		}
		Writer& operator << (long double x)
		{
			if (x < 0) putchar('-'), x = -x;
			mxdouble _ = x;
			x -= (long double)_;
			static short sta[40];
			short top = 0;
			while (_ > 0) sta[++top] = _ % 10, _ /= 10;
			if (top == 0) putchar('0');
			while (top > 0) putchar(sta[top] + '0'), top--;
			putchar('.');
			for (int i = 0; i < Setprecision; i++) x *= 10;
			_ = x;
			while (_ > 0) sta[++top] = _ % 10, _ /= 10;
			for (int i = 0; i < Setprecision - top; i++) putchar('0');
			while (top > 0) putchar(sta[top] + '0'), top--;
			return *this;
		}
		Writer& operator << (__float128 x)
		{
			if (x < 0) putchar('-'), x = -x;
			mxdouble _ = x;
			x -= (__float128)_;
			static short sta[40];
			short top = 0;
			while (_ > 0) sta[++top] = _ % 10, _ /= 10;
			if (top == 0) putchar('0');
			while (top > 0) putchar(sta[top] + '0'), top--;
			putchar('.');
			for (int i = 0; i < Setprecision; i++) x *= 10;
			_ = x;
			while (_ > 0) sta[++top] = _ % 10, _ /= 10;
			for (int i = 0; i < Setprecision - top; i++) putchar('0');
			while (top > 0) putchar(sta[top] + '0'), top--;
			return *this;
		}
		Writer& operator << (char c) { putchar(c); return *this; }
		Writer& operator << (char *str)
		{
			int cur = 0;
			while (str[cur]) putchar(str[cur++]);
			return *this;
		}
		Writer& operator << (const char *str)
		{
			int cur = 0;
			while (str[cur]) putchar(str[cur++]);
			return *this;
		}
		Writer& operator << (string str)
		{
			int st = 0, ed = str.size();
			while (st < ed) putchar(str[st++]);
			return *this;
		}
		Writer() {}
	} cout;
}
using namespace Fastio;
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
static int qg(int l,int r,int x){
    if(l>r)return 0;
    int il=bl[l],ir=bl[r],res=0;
    if(il==ir){
        for(int i=l;i<=r;i++)if(act[i]&&a[i]>x)res++;
        return res;
    }
    for(int i=l;i<=ed[il];i++)if(act[i]&&a[i]>x)res++;
    for(int i=il+1;i<ir;i++)res+=v[i].end()-upper_bound(v[i].begin(),v[i].end(),x);
    for(int i=st[ir];i<=r;i++)if(act[i]&&a[i]>x)res++;
    return res;
}

static int ql(int l,int r,int x){
    if(l>r)return 0;
    int il=bl[l],ir=bl[r],res=0;
    if(il==ir){
        for(int i=l;i<=r;i++)if(act[i]&&a[i]<x)res++;
        return res;
    }
    for(int i=l;i<=ed[il];i++)if(act[i]&&a[i]<x)res++;
    for(int i=il+1;i<ir;i++)res+=lower_bound(v[i].begin(),v[i].end(),x)-v[i].begin();
    for(int i=st[ir];i<=r;i++)if(act[i]&&a[i]<x)res++;
    return res;
}

int main(){
    static int n,m;
    cin>>n>>m;
    tot=(n-1)/mx+1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        p[a[i]]=i;
    }
    for(int i=1;i<=m;i++)cin>>d[i];
    for(int i=1;i<=tot;i++){
        st[i]=(i-1)*mx+1;
        ed[i]=min(i*mx,n);
        for(int j=st[i];j<=ed[i];j++)bl[j]=i;
    }
    fill(act+1,act+n+1,1);
    for(int i=1;i<=n;i++)v[bl[i]].push_back(a[i]);
    for(int i=1;i<=tot;i++)sort(v[i].begin(),v[i].end());
    ans=0;
    for(int i=1;i<=n;i++)ans+=qg(1,i-1,a[i]);
    static vector<long long>res(m+1);
    res[1]=ans;
    for(int i=1;i<=m;i++){
        int val=d[i],pos=p[val],lf=qg(1,pos-1,a[pos]),rt=ql(pos+1,n,a[pos]);
        ans-=lf+rt;
        int id=bl[pos];
        act[pos]=0;
        v[id].erase(lower_bound(v[id].begin(),v[id].end(),a[pos]));
        if(i<m)res[i+1]=ans;
    }
    for(int i=1;i<=m;i++)cout<<res[i]<<endl;
    return 0;
}
C++98 下最高点 672ms672ms，求卡常

回复

共 52 条回复，欢迎继续交流。

正在加载回复...