「睿琪杯」浙江省第 23 届大学生程序设计竞赛 题解

好像网上还没有2026ZJCPC的题解水一篇J我们先来考虑一个问题对于每一个询问mat i,j的值取决于什么答案很显然是 第i行有关的修改 和 第j列有关的修改 中距离当前时间最近的那一个现在我们遇到的第一个问题是每一个修改都有可能对已经发生的修改产生影响所以如果我们能够知道对于每一次插入的数它们最终会在哪一行/列问题就会好处理很多如何得到我们考虑逆处理倒着遍历操作序列初始所有位置都被占用1.假设遇到的是操作1输入 x,y 表示在x行添加值为y的数此时的第 x 行等价 前面有 x 个数的位置被占用也就是说该操作行的最终位置等价 前面有x个位置被占用的第一个位置我们来考虑怎么求这个位置树状数组二分tips:树状数组二分的思路类似倍增法我们知道在树状数组中tree[i]存储的是[i-lowbit(i),i]的和初始位置(idx)0;我们从高到低遍历每一个二进制位因为我们需要找到 有 x 个被占用的位置所以如果当前这个tree[i]存储的x的个数小于k,就令位置加上这个区间值同时将k(目标值)减少反之则不做处理由树状数组的性质当前idxi 的lowbit 一定是 i,所以tree[idxi]的值就是当前x 被占用的个数为什么因为i从大到小遍历比如 8412,lowbit(124于是我们求出了这个位置记录第i次操作对应的最终值同时开数组记录这个最终位置的值和时间戳2.列同理现在我们有了每次操作的最终位置和那个位置对应的信息正序遍历插入操作在对应的数组数组位置插数插的是最终位置这样不会影响其他操作对于查询我们同样使用树状数组二分分别查找行/列中有x/y个数被占用的位置比较时间输出code:#includebits/stdc.h#define int long long#define inf 0x3f3f3f3f3f3f3f#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define cnot coutNO\n#define cyes coutYES\n#define cans coutans\n#define pb push_back#define x0 first#define y0 second#define lc p1#define rc p1|1#define mem(a,b) memset(a,b,sizeof(a))#define sp(x) fixedsetprecision(x)#define all(v) v.begin(),v.end()#define fr(i,st,ed) for(int ist;ied;i)#define ffr(i,st,ed,dt) for(int ist;ied;idt)using namespace std;typedef pairint,stringPis;typedef pairint,intPii;typedef pairstring,stringPss;const int N2e410,mod1e97,M1e610;int lowbit(int x){return x(-x);}int n,c;struct Q{int op,x,y;};struct V{int tim,val;};struct F{int n;vectorinttree;F(int n):n(n),tree(n1,0){}void add(int idx,int val){while(idxn){tree[idx]val;idxlowbit(idx);}}int find(int k){int idx0;int tagk;for(int i31;i0;i--){if(idx(1LLi)ntree[idx(1LLi)]tag){idx(1LLi);tag-tree[idx];}}return idx1;}};void solve(){cinnc;vectorQvec(n1);int cntx0,cnty0;fr(i,1,n){cinvec[i].opvec[i].xvec[i].y;if(vec[i].op1)cntx;if(vec[i].op2)cnty;}vectorintfp(n1);vectorVfvx(n1),fvy(n1);F fx(n1);F fy(n1);fr(i,1,n)fx.add(i,1),fy.add(i,1);int Fp0x,Fp0y;for(int in;i1;i--){if(vec[i].op1){int fposfx.find(vec[i].x1);fp[i]fpos;fx.add(fpos,-1);fvx[fpos]{i,vec[i].y};}if(vec[i].op2){int fposfy.find(vec[i].x1);fp[i]fpos;fy.add(fpos,-1);fvy[fpos]{i,vec[i].y};}}int fp1fx.find(1);int fp2fy.find(1);Fp0xfp1,Fp0yfp2;fvx[fp1]{0,c};fvy[fp2]{0,c};F fa(cntx1),fb(cnty1);fa.add(Fp0x,1);fb.add(Fp0y,1);fr(i,1,n){if(vec[i].op1){fa.add(fp[i],1);}else if(vec[i].op2){fb.add(fp[i],1);}else{int Xfa.find(vec[i].x);int Yfb.find(vec[i].y);int txfvx[X].tim;int tyfvy[Y].tim;if(txty){coutfvx[X].val\n;}else{coutfvy[Y].val\n;}}}}signed main(){GG;int _t1;//cin_t;while(_t--){solve();}}F#includebits/stdc.h#define int long long#define inf 0x3f3f3f3f3f3f3f#define GG ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define cnot coutNO\n#define cyes coutYES\n#define cans coutans\n#define pb push_back#define x0 first#define y0 second#define lc p1#define rc p1|1#define mem(a,b) memset(a,b,sizeof(a))#define sp(x) fixedsetprecision(x)#define all(v) v.begin(),v.end()#define fr(i,st,ed) for(int ist;ied;i)#define ffr(i,st,ed,dt) for(int ist;ied;idt)using namespace std;typedef pairint,stringPis;typedef pairint,intPii;typedef pairstring,stringPss;const int N2e410,mod1e97,M1e610;int lowbit(int x){return x(-x);}void solve(){int n,r;cinnr;vectorintcnt;if(rn) cnt.resize(r1,0);vectorinta(n1),pre(n1,0);fr(i,1,n){cina[i];pre[i]pre[i-1]a[i];}vectorintval(n1);fr(i,1,n)cinval[i];int cur0;vectorintdp(n1,inf);dp[0]0;priority_queuePii,vectorPii,greaterPiiq;int l1;bool f0;fr(i,1,n){if(pre[i]%r0)f1;if(rn){if(cnt[pre[i]%r]1)cur;while(licurr){if(--cnt[pre[l]%r]0)cur--;}}else l1;q.push({dp[i-1]val[i],i});while(!q.empty()q.top().y0l){q.pop();}dp[i]q.top().x0;if(!f)dp[i]0;}coutdp[n]\n;}signed main(){GG;int _t1;cin_t;while(_t--){solve();}}