题解 - Vijos

0

Goodhao LV 10 @ 2017-04-23 07:36:22

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)


const int maxn=100000+10,maxm=1000000+10;
const int inf=0x3f3f3f3f;
int n,m;
struct info {
    int v,pos;
} a[maxn];
struct data {
    int pos;
    int l,r,k,w;
    int ans,ans2;
} q[maxm];
bool cmp(info x,info y) {
    return x.v<y.v;
}
bool cmp2(data x,data y) {
    return x.k<y.k;
}
bool cmp3(info x,info y) {
    return !cmp(x,y);
}
bool cmp4(data x,data y) {
    return x.w>y.w;
}
bool cmp5(data x,data y) {
    return x.pos<y.pos;
}
int c[maxn];
int lowbit(int x) {
    return x&-x;
}
void add(int x,int v) {
    while (x<=n) {
        c[x]+=v;
        x+=lowbit(x);
    }
}
int sum(int x) {
    int res=0;
    while (x>=1) {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
int query(int l,int r) {
    return sum(r)-sum(l-1);
}
int main() {
    scanf("%d%d",&n,&m);
    FOR(i,n) {
        scanf("%d",&a[i].v);
        a[i].pos=i;
    }
    FOR(i,m) {
        scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].k,&q[i].w);
        q[i].pos=i;
    }
    sort(a+1,a+1+n,cmp);
    sort(q+1,q+1+m,cmp2);
    int now=1;
    FOR(i,n) {
        while (now<=m&&q[now].k<=a[i].v) {
            int l=q[now].l,r=q[now].r;
            q[now].ans=query(l,r);
            now++;
        }
        add(a[i].pos,1);
    }
    if (now<=m) {
        int l=q[now].l,r=q[now].r;
        q[now].ans=query(l,r);
    }
    
    memset(c,0,sizeof(c));
    
    sort(a+1,a+1+n,cmp3);
    sort(q+1,q+1+m,cmp4);
    now=1;
    FOR(i,n) {
        while (now<=m&&q[now].w>=a[i].v) {
            int l=q[now].l,r=q[now].r;
            q[now].ans2=query(l,r);
            now++;
        }
        add(a[i].pos,1);
    }
    if (now<=m) {
        int l=q[now].l,r=q[now].r;
        q[now].ans2=query(l,r);
    }
    
    sort(q+1,q+1+m,cmp5);
    FOR(i,m) {
        //cout<<q[i].l<<" "<<q[i].r<<endl;
        printf("%d\n",q[i].r-q[i].l+1-q[i].ans-q[i].ans2);
    }
    return 0;
}

第二道离线处理询问的题目
把在[k,w]中的数的个数转化成总数减去<k的数个数和>w的数个数

0

WeiSama LV 8 @ 2017-02-03 18:04:57

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

const int N = 100000 + 5, M = 2000000 + 5;

int n, m, cnt, tot, a[M], x[M], num[M], ymin[M], ymax[M], nxt[M], ans[M], bit[M], ds[M];

void get_int(int &x)
{
char c= getchar();
while(c==' '||c=='\n')
{
c=getchar();
}
x=c-'0';
while((c=getchar())!=' '&&c!='\n')
{
x=x*10+c-'0';
}
}

inline void add(int x) {
while (x <= n) {
bit[x]++;
x += x & (-x);
}
}

inline int GetSum(int x) {
int ret = 0;
while (x) {
ret += bit[x];
x -= x & (-x);
}
return ret;
}

int main() {
get_int(n), get_int(m);
for (int i = 1; i <= n; i++) {
get_int(a[i]);
ds[i] = a[i];
}
sort(ds + 1, ds + n + 1);
tot = unique(ds + 1, ds + n + 1) - ds - 1;
for (int i = 1; i <= m; i++) {
int l, r, k, w;
get_int(l), get_int(r),get_int(k),get_int(w);
if (l > r) swap(l, r); if (k > w) swap(k, w);
ymin[++cnt] = k, ymax[cnt] = w, nxt[cnt] = x[l - 1], x[l - 1] = cnt, num[cnt] = i;
ymin[++cnt] = k, ymax[cnt] = w, nxt[cnt] = x[r], x[r] = cnt, num[cnt] = i;
}
for (int i = 1; i <= n; i++) {
add(lower_bound(ds + 1, ds + tot + 1, a[i]) - ds);
for (int j = x[i]; j; j = nxt[j]) {
int y1 = lower_bound(ds + 1, ds + tot + 1, ymin[j]) - ds;
int y2 = lower_bound(ds + 1, ds + tot + 1, ymax[j]) - ds;
if (ds[y2] > ymax[j]) y2--;
if (ans[num[j]]) ans[num[j]] = GetSum(y2) - GetSum(y1 - 1) - ans[num[j]];
else ans[num[j]] = GetSum(y2) - GetSum(y1 - 1);
}
}
for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
return 0;
}
时限。还要加输入挂。。
把一段时间的两个端点分开，然后按时间序从左到右扫，左端点记录发生在时间区间[1,l-1]内符合询问要求的点的个数，然后右端点[1,r]也这样搞一次，再把两个减一下。

0

ljt12138 LV 10 @ 2016-10-04 14:15:43

实现！实现！不在实现中爆发，就在实现中灭亡！

出题人：这个题要有离散化，加上树状数组，要排序后计算，还要考读入优化。对了，顺便卡边界。
蒟蒻：这就是个题，泥放过他吧。。
丑陋代码预警！！

#include <bits/stdc++.h>
using namespace std;


// -------------------
typedef long long ll;
ll n, a[100005], ls[100005], nl;
ll m;
struct q {
    ll num, l, r, k, w, ans;
    void print()
    {
        printf("%lld %lld %lld %lld %lld %lld\n", num, l, r, k, w, ans);
    }
}qs[1000005], qs2[1000005];

inline ll read()
{
    ll a = 0;
    int c;
    do c = getchar(); while(!isdigit(c));
    while (isdigit(c)) {
        a = a*10+c-'0';
        c = getchar();
    }
    //scanf("%lld", &a);
    return a;
}

ll c[100005];

inline ll lowbit(ll i)
{
    return i&(-i);
}

void add(int i)
{
    if (i > n) return;
    c[i]++;
    add(i+lowbit(i));
}

ll sum(ll i)
{
    return i?c[i]+sum(i-lowbit(i)):0;
}

ll ans(ll k, ll w)
{
    return sum(w)-sum(k-1);
}

bool cmp1(q a, q b)
{
    return a.r < b.r;
}

bool cmp2(q a, q b)
{
    return a.l < b.l;
}

bool cmp3(q a, q b)
{
    return a.num < b.num;
}

// ---------------------
int vall(ll j)
{
        if (j > ls[nl])
                return nl;
        if (j < ls[1])
                return 1;
        //if (ls[r+1] == j) r += 1;
        return lower_bound(ls+1, ls+nl+1, j)-ls;
}
int valr(ll j)
{
        if (j > ls[nl])
                return nl;
        if (j < ls[1])
                return 1;
        //if (ls[r+1] == j) r += 1;
        int k = lower_bound(ls+1, ls+nl+1, j)-ls;
        if (ls[k] > j) k--;
        return k;
}
// ---------------------
int main()
{
    memset(c, 0, sizeof c);
    memset(a, 0, sizeof a);
    //push(3, 5); push(44444444444, 6);
    //cout << val(3) << " " << val(44444444444) << endl;
    n = read(); m = read();
    for (int i = 1; i <= n; i++)
        ls[i] = a[i] = read();
        sort(ls+1, ls+n+1);
        nl = unique(ls+1, ls+n+1)-ls-1;
       // for (int i = 1; i <= n; i++)
       //         cout << vall(a[i])  << " ";
        //cout << endl;
    for (int i = 1; i <= m; i++)
        qs2[i] = qs[i] = {i, read(), read(), vall(read()), valr(read()), 0};
    sort(qs+1, qs+m+1, cmp2);
    sort(qs2+1, qs2+m+1, cmp1);
    /*for (int i = 1; i <= m; i++) {
        //printf("%lld\n", qs2[i].ans - qs[i].ans);
        qs[i].print();
        qs2[i].print();
    }*/
    int l1 = 1, l2 = 1;
    for (int i = 1; i <= n; i++) {
        while (qs[l1].l <= i && l1 <= m) {
            qs[l1].ans = ans(qs[l1].k, qs[l1].w);
            //cout << "left -- " << i << " -- ";
            //qs[l1].print();
            l1++;
        }
        add(vall(a[i]));
        while (qs2[l2].r <= i && l2 <= m) {
            qs2[l2].ans = ans(qs2[l2].k, qs2[l2].w);
            //cout << "right -- " << i << " -- ";
            //qs2[l2].print();
            l2++;
        }
    }
    //cout << c[2] << endl;
    sort(qs+1, qs+m+1, cmp3);
    sort(qs2+1, qs2+m+1, cmp3);
    for (int i = 1; i <= m; i++) {
        printf("%lld\n", max(0ll, qs2[i].ans - qs[i].ans));
        //qs[i].print();
        //qs2[i].print();
    }
    return 0;
}

0

140142 LV 9 @ 2015-03-25 19:10:19

好不容易A了这道题。。。基本是擦着TLE的门槛了

(为了一点访问量)我把题解放在博客上了(笑)
传送门
http://blog.csdn.net/ww140142/article/details/44498779
思路基本同@Glaceon08的一样(就是照着题解写的啦！)
C++党

0

maxdumbledore LV 9 @ 2015-02-18 23:03:25

我想到的方法和第一种居然不谋而合。。（开始还觉得我的想法很奇怪。。），不过每次都差一两个点a不掉。。。看来还是代码写太烂了。。
不过楼下的方法好赞啊，虽然不知道效率如何

0

Glaceon08 LV 9 @ 2015-02-17 21:50:03

一个比LS更逗比的做法……
同样很意外自己能过……
首先，询问[k,w]的数出现次数就等价于[1,w]的数出现次数减去[1,k-1]的数出现次数。
因此可以对询问的数区间端点进行排序（也就是离线……
然后把给出的数也排序后从小到大插入到应该插入的位置上，
开树状数组（线段树也行）维护[1,i]上数的个数，
并在插入的同时解决沿途的询问……
询问第l天到第r天就等价于1到r天的答案减去1到l-1天的答案，（用线段树的话可以无视这句话>_<）

==============================================================<
时间复杂度的话，真正的瓶颈在于O(mlogm)的询问排序。
所以说这一看就不像真▪正解嘛……………………
PS：不贴代码了……P党代码因附带两个多关键字排序而极为丑陋QAQ

quailty @ 2015-02-17 22:15:11

orz......
quailty @ 2015-02-17 23:24:02

貌似你的算法要更快一些吧......
140142 @ 2015-03-02 14:29:12

orz。。。有点没有看懂
开树状数组（线段树也行）维护[1,i]上数的个数
这句话中i是指什么？
是那个次数吗？那10^9内存不就不够了吗。。。
还是日期什么的？

0

quailty LV 9 @ 2015-02-17 16:39:37

线段树的每个节点记录当前区间内所有数的一个不降序列，
建树时的排序过程可以从叶节点开始向上归并，
查询时找到对应区间后可以直接用lower_bound
和upper_bound函数统计该区间内满足条件的元素个数，
总时间复杂度O(nlogn+m(logn)^2)，空间复杂度O(nlogn)

附上代码：http://paste.ubuntu.com/10269885/

quailty @ 2015-02-17 16:41:14

其实我也挺意外的……居然能过……

题解

7 条题解

漫长的等待

信息

状态

开发

支持

题解

7 条题解

漫长的等待

信息

状态

开发

支持

还没有账户？

登录