网站发布方式有哪些,国内旅行做行程网站,德州哪个做网站做得好,建程网工程平台Description 见EOJ439 Solution 先考虑不强制在线怎么做。 按询问区间右端点排序#xff0c;从左往右扫#xff0c;维护所有后缀的答案。 如果扫到 \(a[i]\)#xff0c;那么让统计个数的 \(cnt[a[i]]\). 如果\(cnt[a[i]]a[i]\)#xff0c;那么在当前的右端点固定的情况…Description 见EOJ439 Solution 先考虑不强制在线怎么做。 按询问区间右端点排序从左往右扫维护所有后缀的答案。 如果扫到 \(a[i]\)那么让统计个数的 \(cnt[a[i]]\). 如果\(cnt[a[i]]a[i]\)那么在当前的右端点固定的情况下这个\(a[i]\)不会有任何的贡献。 如果\(cnt[a[i]]a[i]\)那么可以让\([1,pre[i]]\)区间加\(1\)其中\(pre[i]\)代表从\(i\)向前第\(a[i]\)个\(a[i]\)出现的位置。 如果\(cnt[a[i]]a[i]\)那么需要让\((pos[pos[pre[i]]],pos[pre[i]]]\)区间减\(1\)其中\(pos[i]\)代表从\(i\)向前第\(1\)个\(a[i]\)出现的位置同时还需要让\((pos[pre[i]],pre[i]]\)区间加\(1\)。 这个放上线段树区间修改单点查询就好了。 但是要求强制在线。 推上主席树。 还要区间修改。 pushdown空间巨大 标记永久化。 Code #includeset
#includemap
#includecmath
#includequeue
#includecctype
#includevector
#includecstdio
#includecstring
#includeiostream
#includealgorithm
using std::min;
using std::max;
using std::swap;
using std::vector;
const int N1e55;
typedef double db;
const int maxn1e5;
typedef long long ll;
#define pb(A) push_back(A)
#define pii std::pairint,int
#define all(A) A.begin(),A.end()
#define mp(A,B) std::make_pair(A,B)vectorint v[N];
int n,q,a[N],sum[N*30],cov[N*30];
int root[N],ch[N*30][2],cnts[N],tot;int getint(){int X0,w0;char ch0;while(!isdigit(ch))w|ch-,chgetchar();while( isdigit(ch))XX*10ch-48,chgetchar();if(w) return -X;return X;
}int modify(int pre,int l,int r,int ql,int qr,int c){int curtot;ch[cur][0]ch[pre][0];ch[cur][1]ch[pre][1];sum[cur]sum[pre]c*(qr-ql1);cov[cur]cov[pre];if(qll and rqr){cov[cur]c;return cur;} int midlr1;if(qrmid) ch[cur][0]modify(ch[pre][0],l,mid,ql,qr,c);else if(qlmid) ch[cur][1]modify(ch[pre][1],mid1,r,ql,qr,c);else{ch[cur][0]modify(ch[pre][0],l,mid,ql,mid,c);ch[cur][1]modify(ch[pre][1],mid1,r,mid1,qr,c);} return cur;
}int query(int cur,int l,int r,int ql,int qr,int add){if(qll and rqr) return sum[cur]add*(r-l1);int midlr1;if(qrmid) return query(ch[cur][0],l,mid,ql,qr,addcov[cur]);else if(qlmid) return query(ch[cur][1],mid1,r,ql,qr,addcov[cur]);else return query(ch[cur][0],l,mid,ql,mid,addcov[cur])query(ch[cur][1],mid1,r,mid1,qr,addcov[cur]);
}signed main(){ngetint(),qgetint();for(int i1;in;i) v[i].pb(0);for(int i1;in;i){a[i]getint();root[i]root[i-1];if(a[i]n)continue;cnts[a[i]];v[a[i]].pb(i);if(cnts[a[i]]a[i])root[i]modify(root[i],1,n,1,v[a[i]][1],1);else if(cnts[a[i]]a[i]){int szev[a[i]].size();root[i]modify(root[i],1,n,v[a[i]][sze-a[i]-2]1,v[a[i]][sze-a[i]-1],-1);root[i]modify(root[i],1,n,v[a[i]][sze-a[i]-1]1,v[a[i]][sze-a[i]],1);}} int lasans0;while(q--){int xgetint()^lasans,ygetint()^lasans;printf(%d\n,lasansquery(root[y],1,n,x,x,0));} return 0;
} 转载于:https://www.cnblogs.com/YoungNeal/p/9857615.html
